## VMWare Inc Interview Question

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
5
of 9 vote

In most cases when the question is related to sub array the Kadane's algorithm is very useful. The real problem in this question is to find largest contiguous sub array for which difference 'numberOfZeros - numberOfOnes' is the biggest to maximize the sum of ones after flipping zeros.
Here is modified version of Kadane's algorithm to do this job.
It converts 0 to -1 and computes the sum till the sum is <=0 (there is more 0s then 1s).
If the sum is > 0 starts from the beginning.
The major difference compare to ordinary Kadane's algorithm is that we are looking for the biggest negative sum instead of positive.
Code:

``````public static void flipBits(int[] a) {

int maxDiff = 0;
int flipStartIndex = 0;
int flipEndIndex = 0;
int onesToFlip = 0;
int totalNumberOfOnes = 0;

int currentDiff = 0;
int currentStart = 0;
int currentOnesToFlip = 0;

for (int i = 0; i < a.length; i++) {
if (a[i] == 0) {
currentDiff -= 1;
} else {
currentDiff += 1;
currentOnesToFlip++;
totalNumberOfOnes++;
}
if (currentDiff < maxDiff) {
maxDiff = currentDiff;
flipStartIndex = currentStart;
flipEndIndex = i;
onesToFlip = currentOnesToFlip;
} else if (currentDiff > 0) {
currentDiff = 0;
currentStart = i + 1;
currentOnesToFlip = 0;
}
}
System.out.println(flipEndIndex - flipStartIndex + 1 - onesToFlip +   totalNumberOfOnes - onesToFlip);
}``````

Space O(1), Time O(n)

Comment hidden because of low score. Click to expand.
0

1, 0, 0, 1, 0, 0, 1,1,1,1, 0,1
Doesn't work for this input.

Comment hidden because of low score. Click to expand.
1
of 1 vote

@Anonymous may I ask why? The function returns 10 which looks like the maximum possible number of 1s after flipping.

Comment hidden because of low score. Click to expand.
0

Please correct me if I am wrong.
This should handle the case of no zeros in the array. In which case, it should return the total number of ones present in the array or even say no zeros found.

``````public static void flip(int a[])
{
int maxdiff=0;
int fsindex=0;
int feindex=0;
int onestoflip=0;
int totalones=0;

int currentdiff=0;
int currentstart=0;
int currentonestoflip=0;
int zerocount=0;
for(int i=0;i<a.length;i++)
{
if(a[i]==0)
{
currentdiff-=1;
zerocount++;
}
else
{
currentdiff+=1;
currentonestoflip++;
totalones++;
}
if(currentdiff<maxdiff)
{
maxdiff=currentdiff;
fsindex=currentstart;
feindex=i;
onestoflip=currentonestoflip;
}
else if(currentdiff>0)
{
currentdiff=0;
currentstart=i+1;
currentonestoflip=0;
}

}
if(zerocount!=0)
System.out.println(feindex - fsindex + 1 - onestoflip + totalones - onestoflip);
else
System.out.println("No zeros to flip, total number of ones"+totalones);
}``````

Comment hidden because of low score. Click to expand.
0

Hi, We can convert 1 to -1 can calculate maximum sum using kadane algorithm. am i right?

Comment hidden because of low score. Click to expand.
0

the line
int flipEndIndex = 0;
should be changed to
int flipEndIndex = -1;

to accommodate for the case of all 1s in input

Comment hidden because of low score. Click to expand.
0

the line
int flipEndIndex = 0;
should be changed to
int flipEndIndex = -1;

to accommodate for the case of all 1s in input

Comment hidden because of low score. Click to expand.
1
of 1 vote

int maximumNumber(vector<int> vec)
{
int max_so_far = 0;
int current_max = 1;
int index = 0;
int end = 0;
for(int i = 0; i < vec.size(); i++)
{
if(vec[i] == 0)
{
current_max++;
end++;
}
else
current_max--;

if(current_max <0)
{
current_max = 0;
index = i;
}

if (current_max < max_so_far)
max_so_far = current_max;

}
return end - index + 1;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void main(String args[]){
int arr[] = {1, 0, 0, 1, 0, 0, 1, 0};
int sum=0,maxsum=0,num=0;
int startIndex=0,stopIndex=0,prevIndex=0;

for(int i=0;i<arr.length;i++){
if(arr[i] == 1){
num = -1;
}else if(arr[i] == 0){
num = 1;
}
sum = sum + num;
if(maxsum<sum){
maxsum = sum;
prevIndex = startIndex;
stopIndex = i;
}else if(sum<0){
sum = 0;
startIndex = i+1;
}
}

for(int j=prevIndex;j<=stopIndex;j++){
System.out.print(" "+arr[j]);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here my solution I looking for maximum interval sum

``````#define maxn 100505
using namespace std;
int n,m,k,x,curn,D[maxn],C[maxn] ;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>C[i];
D[i] = D[i-1] + C[i];
if(C[i] == 0)
C[i]=1;
else C[i]=-1;
}
int ini = 1,fin=1;
int sum = C[1];
int res = C[1];
int x=1,y=1;
while(ini <= n)
{
if(sum > res)
{
res = sum;
x = ini;
y = fin;
}
if(sum < 0)
{
if(fin <= n){
fin++;
sum=C[fin];
}
ini = fin;
}else{
if(fin<=n){
fin++;
sum+=C[fin];
}else
{
sum-=C[ini];
ini++;
}
}
}
cout<<D[x-1] + D[n] - D[y] + res + ( (y-x+1) - res) / 2;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Idea is simple, we will solve it like maximum sub array problem. All you need it is to change 1 to -1 and 0 to 1. So maximum subarray will be the answer . Then you build up array where c[i] is sum from 0 to i. Then you iterate over this array, for each j position answer will be cumul[j] - cumul[k], where k is a position of minimum element from left to i. We need to know this minimum and update it when it changes. Answer - pair of k and j, which have produced maximum difference of cumul[j] - cumul[k].

``````def cumulative(a):
output = [a[0]]

for i in range(1,len(a)):
output.append(output[i - 1] + a[i])

return output

def prepare(a):
b = a
for i in range(0,len(a)):
if b[i] == 1:
b[i] = -1
else:
b[i] = 1
return b

def sub_array(a):
cumul = cumulative(a)
a = prepare(a)

left = 0 #Current left minimum position
left_global = 0#Global left minimum position
right = 0# right side of maximal interval
left_min = 999999#left min value
global_max = -999999#global max value
right = 0

for r in range(0,len(a)):
#if current sum if bigger then previous
if cumul[r] - left_min > global_max:
global_max = cumul[r] - left_min
right = r
left_global = left + 1
#if current element cumulative sum if bigger than prevous minimum
if cumul[r] < left_min:
left = r
left_min = cumul[r]

return (left_global,right)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.*;

public class Solution {

public static void main(String[] args) {
System.out.print("Enter array size: ");

System.out.println("Enter sequence: ");

if(arrayStr.length != length) {
throw new Exception(String.format("Size of N - <%d> and size of Array - <%d> differ.", length, arrayStr.length));
}

int max = 0;
int L = 0;
int Lmax = 0;
int Rmax = 0;
int current = 0;
for(int i = 0; i < length; i++) {
if(arrayStr[i].equals("0")) {
current++;
} else {
current--;
}

if(current <= 0) {
L = i;
} else if(current > max) {
Lmax = L;
Rmax = i;
max = current;
}
}

int[] tmpArray = flip(arrayStr, Lmax, Rmax);

int aces = 0;
for(int k = 0; k < length; k++) {
if(tmpArray[k] == 1) aces++;
}
System.out.println(Lmax + " - " + Rmax);
System.out.println(aces);
} catch(Exception e) {
e.printStackTrace();
}
}

private static int[] flip(String[] array, int L, int R) throws Exception {

int length = array.length;

int[] arrayInt = new int[array.length];
for(int i = 0; i < array.length; i++) {
arrayInt[i] = Integer.parseInt(array[i].trim());
}

if(L > length || L < 0 || R > length || R < 0 || L > R) {
throw new Exception("Constraint: 0 <= L <= R < n");
}

for(int i = L; i <= R; i++) {
arrayInt[i] ^= 1;
}

return arrayInt;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.*;

public class Solution {

public static void main(String[] args) {
System.out.print("Enter array size: ");

System.out.println("Enter sequence: ");

if(arrayStr.length != length) {
throw new Exception(String.format("Size of N - <%d> and size of Array - <%d> differ.", length, arrayStr.length));
}

int max = 0;
int L = 0;
int Lmax = 0;
int Rmax = 0;
int current = 0;
for(int i = 0; i < length; i++) {
if(arrayStr[i].equals("0")) {
current++;
} else {
current--;
}

if(current <= 0) {
L = i;
} else if(current > max) {
Lmax = L;
Rmax = i;
max = current;
}
}

int[] tmpArray = flip(arrayStr, Lmax, Rmax);

int aces = 0;
for(int k = 0; k < length; k++) {
if(tmpArray[k] == 1) aces++;
}
System.out.println(Lmax + " - " + Rmax);
System.out.println(aces);
} catch(Exception e) {
e.printStackTrace();
}
}

private static int[] flip(String[] array, int L, int R) throws Exception {

int length = array.length;

int[] arrayInt = new int[array.length];
for(int i = 0; i < array.length; i++) {
arrayInt[i] = Integer.parseInt(array[i].trim());
}

if(L > length || L < 0 || R > length || R < 0 || L > R) {
throw new Exception("Constraint: 0 <= L <= R < n");
}

for(int i = L; i <= R; i++) {
arrayInt[i] ^= 1;
}

return arrayInt;
}
}``````

Comment hidden because of low score. Click to expand.
0

Above code is returning 4 instead of 6 as an output

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
def result(arr):
maxcount = 0
ones = 0
count = 0
for i in range(len(arr)):
if (arr[i] == 0):
count += 1
else:
count -= 1
ones += 1

if (count > maxcount):
maxcount = count

if (count < 0):
count = 0
return maxcount + ones
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{def result(arr):
maxcount = 0
ones = 0
count = 0
for i in range(len(arr)):
if (arr[i] == 0):
count += 1
else:
count -= 1
ones += 1

if (count > maxcount):
maxcount = count

if (count < 0):
count = 0
return maxcount + ones }}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int main()
{
int n,i;
int *arr;
int startIndex=-1;
int endIndex = -1;
int countOnes=0;
int sum =0, max=0,subtractSum=0;

scanf("%d",&n);
arr = (int *)malloc(sizeof(int)*n);
for(i=0;i<n;i++) {
scanf("%d",&arr[i]);
}
for(i=0;i<n;i++) {
if(arr[i] == 1 && startIndex == -1) {
countOnes++;
continue;
}
else if((sum - subtractSum) <= 0 && startIndex != -1) {
startIndex = i;
subtractSum =0;
sum = 0;
}
else if(arr[i] == 0) {
if(startIndex == -1) {
startIndex = i;
}
sum++;
}
else if(arr[i] == 1){
subtractSum++;
}
if(sum > max) {
max = sum;
endIndex = i;
}
}
if(endIndex==-1)
endIndex = i;
else if(startIndex != endIndex)
endIndex++;
for(i=endIndex;i<n;i++) {
if(arr[i] == 1) {
countOnes++;
}
}
printf("%d",countOnes+max);
return 0;

Comment hidden because of low score. Click to expand.
0
of 0 vote

Following is bruit-force cum semi-dynamic solution. R[N-1][N-1] matrix stores the number of 1s for each iteration. The stored R matrix can be used in computation to optimize the solution via dynamic-programming.

Assume Given
N=8
A[0...7] = {1,0,0,1,0,0,1,0}

``````R[N-1][N-1] = {0};
for (int i = 0; i < N-1; ++i) {
for (int j = N-1; j > i; --j) {
int k = i;
while (k < j) {
if (!A[k]) {
R[i][j]++;
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Following is bruit-force cum semi-dynamic solution. R[N-1][N-1] matrix stores the number of 1s for each iteration. The stored R matrix can be used in computation to optimize the solution via dynamic-programming.

Assume Given
N=8
A[0...7] = {1,0,0,1,0,0,1,0}

``````R[N-1][N-1] = {0};
for (int i = 0; i < N-1; ++i) {
for (int j = N-1; j > i; --j) {
int k = i;
while (k < j) {
if (!A[k]) {
R[i][j]++;
}
}
}
}
return max{R[i][j]; where 0 < i < N-1 and 0 < j < N-1}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the best/optimum solution through dynamic-programming...

Assume Given
N=8
A[0...7] = {1,0,0,1,0,0,1,0}

``````int Zeros (int A[], int i, int j) {
int countZeros = 0;
if (i < j) {
for (int k = i, k < j; ++k) {
if (!A[k]) {
countZeros++;
}
}
}
return countZeros;

}

int R[N-1][N-1] = {-1};

int flip (int A[], int R[][], int i, int j) {
if (i < j) {
if (R[i][j] != -1) {
return R[i][j];
} else {
R[i][j] = max{ Zeros(A, i, j),
1&A[i] + flip(A, R, i+1, j),
flip(A, R, i, j-1) + 1&A[j],
1& A[i] + flip(A, R, i+1, j-1) + 1&A[j]
};
}
} else if (i == j){
return !A[i];
} else {
return 0;
}
return R[i][j];
}

int main () {
printf("Max Number of 1s: ", flip (A, R, 0, N-1));
}``````

Comment hidden because of low score. Click to expand.
0

In above code, replace call to function f() by flip().

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct res_s
{
int i;
int j;
int sum;
}res_t;

res_t find_sub_array(int* a, int size)
{
res_t max = {0};
res_t maxcur = {0};
res_t* maxsub = NULL;
int i;

maxsub = (res_t*)calloc(sizeof(res_t),size);
max.i= -1*1000;
maxcur.i=max.i;

for(i=0; i<size;++i)
{
if(maxcur.sum < 0)
{
maxcur.sum =a[i];
maxcur.i =i;
maxcur.j =i;
}
else
{
maxcur.sum+=a[i];
maxcur.j = i;
}

if(maxcur.sum > max.sum)
max = maxcur;

maxsub[i] = max;
}
return maxsub[size-1];
}

/*
* calc max sum based on start and end indexes found
* flip bits in [s,e] range, before ocunting
*/
int calc_sum(int* a,  int n, int s, int e)
{
int i,sum = 0;

for(i=0; i< n;++i)
{
if((i < s) || (i > e))
{
}

if(i >=s && i <= e)
{
if(0 == a[i])
}
}

return sum;

}
int main()
{
int o[] = {1,0,0,1,0,0,1,0};
int b[] = {-1,1,1,-1,1,1,-1,1};
//int a[] = {-1,-2,3,4,-5,6};

res_t rest = find_sub_array(b, 8);

printf("%d,%d=%d\n", rest.i, rest.j, calc_sum(o, 8, rest.i, rest.j));

return;
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

1 #include<iostream>
2 using namespace std;
3
4 int calOnes(int *ptr,int);
5
6 int main()
7 {
8 int a[]={0,1,0,1,0,1,0,1,0,1,0,0,1,1};
9 //int a[]={1,0,1,0,0,0,1,0,0,1,1,1,1,0,0,1,1,1,0,0,0,1};
10 int i=calOnes(a,sizeof(a)/sizeof(a[0]));
11
12 cout<<i<<endl;
13
14 }
15
16 int calOnes(int *ptr,int len)
17 {
18 int max_diff = 0;
19 int i;
20 int diff = 0;
21 int orig_ones =0;
22 int zero2one=0;
23 int one2zero=0;
24 for(i = 0;i < len;i++)
25 {
26
27
28 if(ptr[i] == 0)
29 {
30 if(diff <= 0)
31 {
32 zero2one = 1;
33 max_diff = zero2one;
34 one2zero = 0;
35 diff = 1;
36 continue;
37 }
38 ++zero2one;
39 }
40 else
41 {
42 ++orig_ones;
43 ++one2zero;
44 }
45 diff = zero2one - one2zero;
46 if( diff > max_diff)
47 max_diff = diff;
48
49
50 }
51 // cout<<max_diff<<" "<<orig_ones;
52 return(max_diff+orig_ones);
53
54 }

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Solution(object):
def maxOne(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums is None or len(nums) == 0:
return 0
max_sum = nums[0]
dp = [0] * len(nums)
dp[0] = -1 if nums[0] == 1 else 1
res = 0
for i, v in enumerate(nums):
if i == 0:
res = res + 1 if v == 1 else 0
continue
if v == 0:
if dp[i-1] > 0:
dp[i] = dp[i-1] + 1
else:
dp[i] = 1
else:
res = res + 1
if dp[i-1] - 1 > 0:
dp[i] = dp[i-1] - 1
else:
dp[i] = 0

max_sum = max(max_sum, dp[i])

return res + max(max_sum, 0)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Solution(object):
def maxOne(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums is None or len(nums) == 0:
return 0
max_sum = nums[0]
dp = [0] * len(nums)
dp[0] = -1 if nums[0] == 1 else 1
res = 0
for i, v in enumerate(nums):
if i == 0:
res = res + 1 if v == 1 else 0
continue
if v == 0:
if dp[i-1] > 0:
dp[i] = dp[i-1] + 1
else:
dp[i] = 1
else:
res = res + 1
if dp[i-1] - 1 > 0:
dp[i] = dp[i-1] - 1
else:
dp[i] = 0

max_sum = max(max_sum, dp[i])

return res + max(max_sum, 0)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class IntFlip {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int num;
int temp1 = 0;
System.out.println("Enter the length of the array");
num = in.nextInt();

int[] Arr = new int[num];
System.out.println("Enter the elements of the array");
for(int i = 0;i<Arr.length;i++)
{
int temp = in.nextInt();
if(temp == 0 || temp == 1)
{
Arr[i] = temp;
}
else
{
System.out.println("Please enter either 0 or 1");
i = i-1;
}
}

int l,r;
System.out.println("Enter the lower limit");
l = in.nextInt();
while(l < 0)
{
l = in.nextInt();
}

System.out.println("Enter the upper limit");
r = in.nextInt();
while(r > Arr.length-1)
{
r = in.nextInt();
}

Flip(Arr,l,r);

System.out.println("Array after flipping");

for(int f = 0;f<Arr.length;f++)
{
System.out.println(Arr[f]);
if(Arr[f] ==1)
{
temp1 = temp1 + 1;
}
}

System.out.println("The number of 1s in the array is" +temp1);

/*System.out.println("The array is as follows");

for(int j=0;j<Arr.length;j++)
{
System.out.println(Arr[j]);

}*/

}
public static void Flip(int[] Array, int left, int Right)
{
for(int k = left;k<=Right;k++)
{
if(Array[k] == 0)
{
Array[k] = 1;

}
else if(Array[k] == 1)
{
Array[k] = 0;
}
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class IntFlip {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int num;
int temp1 = 0;
System.out.println("Enter the length of the array");
num = in.nextInt();

int[] Arr = new int[num];
System.out.println("Enter the elements of the array");
for(int i = 0;i<Arr.length;i++)
{
int temp = in.nextInt();
if(temp == 0 || temp == 1)
{
Arr[i] = temp;
}
else
{
System.out.println("Please enter either 0 or 1");
i = i-1;
}
}

int l,r;
System.out.println("Enter the lower limit");
l = in.nextInt();
while(l < 0)
{
l = in.nextInt();
}

System.out.println("Enter the upper limit");
r = in.nextInt();
while(r > Arr.length-1)
{
r = in.nextInt();
}

Flip(Arr,l,r);

System.out.println("Array after flipping");

for(int f = 0;f<Arr.length;f++)
{
System.out.println(Arr[f]);
if(Arr[f] ==1)
{
temp1 = temp1 + 1;
}
}

System.out.println("The number of 1s in the array is" +temp1);

/*System.out.println("The array is as follows");

for(int j=0;j<Arr.length;j++)
{
System.out.println(Arr[j]);

}*/

}
public static void Flip(int[] Array, int left, int Right)
{
for(int k = left;k<=Right;k++)
{
if(Array[k] == 0)
{
Array[k] = 1;

}
else if(Array[k] == 1)
{
Array[k] = 0;
}
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why everything so complected. should run max one's.. check this solution.

``````int bitRotate() {
int L = 1, R = 5;
int size = 8;
int arr[8] = { 1, 0, 0, 1, 0, 0, 1, 0 };

int count = 0;
for (int i = 0; i < 8; i++){
if (i >= L && i <= R)
arr[i] = !arr[i];

if (arr[i] == 1) count++;
}
return count;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int bitRotate() {
int L = 1, R = 5;
int size = 8;
int arr[8] = { 1, 0, 0, 1, 0, 0, 1, 0 };

int count = 0;
for (int i = 0; i < 8; i++){
if (i >= L && i <= R)
arr[i] = !arr[i];

if (arr[i] == 1) count++;
}
return count;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<stdio.h>
#include<stdbool.h>
int flipbits(bool arr[], int n)
{
// For the example 0 0 0 1 0 1
int i,origOnes=0,count=0;
int value[10000];

for(i=0;i<n;i++)
{
if(arr[i]==1)
{
origOnes=origOnes+1;
value[i]=1;
}
else if(arr[i]==0)
{
value[i]=-1;

}
//It now becomes -1 -1 -1 1 -1 1
//Now Flip the bits and find maximum contiguous array
}

for(i=0;i<n;i++)
{
if(arr[i]==true)
count++;
}
if(count==n)
{
return count;
}

for(i=0;i<n;i++)
{
value[i] = -value[i];
}

//Now, the array becomes 1 1 1 -1 1 -1
//Here comes the fun part, Just apply Kandane's algorithm
//and find the maximum contiguous sub-array
int MaxSoFar=-99999, MaxEndingHere=0;
for(i=0;i<n;i++)
{
MaxEndingHere = MaxEndingHere + value[i];
if(MaxEndingHere>MaxSoFar)
MaxSoFar = MaxEndingHere;
if(MaxEndingHere<0)
MaxEndingHere=0;
}
//Now we know maximum contiguous sub-array is from arr[0] to arr[4]
//I guess we flip everything back to normal? no!
//We know MaxSoFar right now is 3
//Number of ones initially was 2
//To get maximum number of ones, ass the original number of ones to MaxSoFar
return (origOnes + MaxSoFar);
}
int main()
{
int a[10000];
bool arr[10000];
int i,j,m,n,ans;
scanf("%d",&m);

for(j=0;j<m;j++)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n;i++)
{
if(a[i]==1)
arr[i]=1;
else if(a[i]==0)
arr[i]=0;
}
ans=flipbits(arr,n);
printf("%d\n",ans);
}

return 0;``````

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

go through the array, while doing it, perform the following:
1. count the number of 1's in your input
2. keep a custom counter +1 if we see a zero, -1 if we see a one, do not count leading 1's
3. use a separate variable to keep track of the max value of your counter
output= max value of your counter + the number of 1's in your input

Comment hidden because of low score. Click to expand.
0

add the 1's which dont occur in this max value and not all the 1's encountered till now

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I use a vector to store the zeros like <position in array, k(kth 0)>
Each time, we only need to check if the continuous two zeros in vector can generate more 1 after flipping. If yes, go ahead. If not, record the max 1 can generate now. And return back to original array and do the same step above.
code is below. O(n)

``````int mostone(int *c, int len){
vector < vector < int >> poszero;
int count = 1;
for (int i = 0; i < len; i++){
if (*(c + i) == 0) poszero.push_back({ i, count++ });
}
vector<int> cur = poszero[0];
vector<int> next;
int change= 0;
int maxone = 0;
count = 1;
int intevl = 0;
for (int i = 1; i < poszero.size(); i++){
next = poszero[i];
//dont include the last zero in this inteval
int increase = (next[1] - cur[1] + 1 - (next[0] - cur[0] + 1 - (next[1] - cur[1] + 1)))-1;
if (increase>=0){
change += increase;
}
else{
maxone = std::max(maxone, change+1); //plus back last one
change = 0;
}
cur = next;
}
return len-poszero.size()+std::max(maxone,change+1);
}``````

Comment hidden because of low score. Click to expand.
-2

Doesn't work for { 0,0,0,0,1,1,1,0,0,0,0 }.
Correct ans is 8, whereas output is 7

Comment hidden because of low score. Click to expand.
-1
of 1 vote

dont know what "1's which dont occur in this max value and not all the 1's encountered till now" means, but rest assured, the math works out in the end.

``````public int ggff(int N, int [] A)
{
int maxctr=0;
int ctr=0;
for (int i=0;i<N;i++)
{
if (A[i]==1)
ctr--;
else ctr++;
if (ctr<maxctr)
maxctr=ctr;

}
if (max<0) /// handle inputs that looks like 111111111...
return 0;
else return maxctr;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

dont know what "1's which dont occur in this max value and not all the 1's encountered till now" means, but rest assured, the math works out in the end.

``````public int ggff(int N, int [] A)
{
int maxctr=0;
int ctr=0;
for (int i=0;i<N;i++)
{
if (A[i]==1)
ctr--;
else ctr++;
if (ctr<maxctr)
maxctr=ctr;

}
if (max<0) /// handle inputs that looks like 111111111...
return 0;
else return maxctr;
}``````

Comment hidden because of low score. Click to expand.
0

typos..

``````public int ggff(int N, int [] A)
{
int maxctr=0;
int ctr=0;
int ones=0;
for (int i=0;i<N;i++)
{
if (A[i]==1)
{ctr--;
ones++;
}
else ctr++;
if (ctr<maxctr)
maxctr=ctr;

}
if (max<0)
return N;
else return maxctr+ones;
}``````

Comment hidden because of low score. Click to expand.
-2

Doesn't work for: {1,1,1,0,0,1,1,1,0,0};

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
-1
of 1 vote

1 0 0 1 0 0 1 0
flip17
1 1 1 0 1 1 0 1
max(1):6
0 0 0 0 1 1 1 0 0 0 0
flip010
1 1 1 1 0 0 0 1 1 1 1
max(1):8

``````#include <iostream>
#include <vector>

int check_begin(const std::vector<int>& vec) {
int cnt_zero;
int cnt_one;

int bigger = 0;
int saved_i;

for(int i = 0; i < vec.size(); i++) {
cnt_one = 0;
cnt_zero = 0;

for(int j = i; j < vec.size(); j++) {
if(vec[j] == 0) {
++cnt_zero;
} else {
++cnt_one;
}
}

int delta = cnt_zero - cnt_one;
if(delta > bigger || bigger == 0) {
bigger = delta;
saved_i = i;
}
}

return saved_i;
}

int check_end(const std::vector<int>& vec, int begin) {
int cnt_zero;
int cnt_one;

int bigger = 0;
int saved_i;

for(int i = vec.size() - 1; i > begin; i--) {
for(int j = begin; j <= i; j++) {
cnt_one = 0;
cnt_zero = 0;

if(vec[j] == 0) {
++cnt_zero;
} else {
++cnt_one;
}
}

int delta = cnt_zero - cnt_one;

if(delta > bigger || bigger == 0) {
bigger = delta;
saved_i = i;
}
}

return saved_i;
}

static void flip(std::vector<int>& vec, int begin, int end) {
std::cout << "flip" << begin << end << std::endl;
for(int i = begin; i <= end; i++) {
if(vec[i] == 0) {
vec[i] = 1;
} else {
vec[i] = 0;
}
}
}

static int count_one(const std::vector<int>& vec) {
int cnt = 0;
for(auto c: vec) {
if(c == 1)
++cnt;
}

return cnt;
}

static void print_vec(const std::vector<int>& vec) {
for(auto c: vec) std::cout << c << " ";
std::cout << std::endl;
}

int main() {
std::vector<int> binvec{1, 0, 0, 1, 0, 0, 1, 0};
std::vector<int> binvec_test{0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0};
int begin, end;

print_vec(binvec);
begin = check_begin(binvec);
end = check_end(binvec, begin);
flip(binvec, begin, end);
print_vec(binvec);
std::cout << "max(1):" << count_one(binvec) << std::endl;

print_vec(binvec_test);
begin = check_begin(binvec_test);
end = check_end(binvec_test, begin);
flip(binvec_test, begin, end);
print_vec(binvec_test);
std::cout << "max(1):" << count_one(binvec_test) << std::endl;

return 0;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.