Repository navigation
Expand file tree
/
Copy pathMainClass.java
More file actions
114 lines (89 loc) · 1.95 KB
/
Copy pathMainClass.java
File metadata and controls
114 lines (89 loc) · 1.95 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
package doubtSession2;
import java.util.*;
public class MainClass {
static int largestSubarraywithEqual0And1(int a[]) {
int n = a.length;
int prefixSum[] = new int[n];
// if(a[0] == 0) {
// prefixSum[0] = -1;
// } else {
// prefixSum[0] = 1;
// }
prefixSum[0] = a[0] == 0 ? -1: 1;
for(int i = 1; i<n; i++) {
prefixSum[i] = a[i] == 0 ?
prefixSum[i-1]-1: prefixSum[i-1]+1;
}
// int a[] = {0, 0, 0, 0, 1, 0, 1, 1, 0, 1};
// prefix[] = {-1, -2, -3, -4, -3, -4, -3, -2, -3, -2}
// ans = 8
//
// -1 -> 0
// -2 -> 1
// -3 -> 2
// -4 -> 3
Map<Integer, Integer> map = new HashMap<>();
int ans = 0;
for(int i = 0; i<n; i++) {
if(map.containsKey(prefixSum[i])) {
ans = Math.max(ans, i - map.get(prefixSum[i]));
} else {
map.put(prefixSum[i], i);
}
}
return ans;
}
static int LongestOnes(int a[]) {
int curCount = 0;
int maxCount = 0;
for(int element: a) {
if(element == 0) {
maxCount = Math.max(maxCount, curCount);
curCount = 0;
} else {
curCount++;
}
}
maxCount = Math.max(maxCount, curCount);
return maxCount;
}
// int a[] = {1, 2, 4, 4, 2, 3};
//
// curElement = 4
// count = 0
static int majorityElement(int a[]) {
int curElement = -1;
int count = 0;
for(int i = 0; i<a.length; i++) {
if(count == 0) {
curElement = a[i];
count = 1;
} else {
if(a[i] == curElement) {
count++;
} else {
count--;
}
}
}
int finalCount = 0;
for(int e: a) {
if(e == curElement) {
finalCount++;
}
}
if(finalCount > a.length / 2) {
return curElement;
} else {
return -1;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
// int a[] = {2, 2, 2, 4, 5, 6, 2, 2, 2, 4};
// System.out.println(majorityElement(a));
// int a[] = {0, 0, 0, 0, 1, 0, 1, 1, 0, 1};
int a[] = {0, 0, 0, 1, 1, 0, 1};
System.out.println(largestSubarraywithEqual0And1(a));
}
}