VMWare Inc Interview Question
Country: United States
Interview Type: Written Test
@Anonymous may I ask why? The function returns 10 which looks like the maximum possible number of 1s after flipping.
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);
}
Hi, We can convert 1 to -1 can calculate maximum sum using kadane algorithm. am i right?
the line
int flipEndIndex = 0;
should be changed to
int flipEndIndex = -1;
to accommodate for the case of all 1s in input
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;
}
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)
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]);
}
}
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] ;
string cad;
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;
}
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)
import java.io.*;
public class Solution {
public static void main(String[] args) {
try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
System.out.print("Enter array size: ");
int length = Integer.parseInt(br.readLine().trim());
System.out.println("Enter sequence: ");
String[] arrayStr = br.readLine().trim().split(" ");
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;
}
}
import java.io.*;
public class Solution {
public static void main(String[] args) {
try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
System.out.print("Enter array size: ");
int length = Integer.parseInt(br.readLine().trim());
System.out.println("Enter sequence: ");
String[] arrayStr = br.readLine().trim().split(" ");
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;
}
}
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;
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]++;
}
}
}
}
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}
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));
}
#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;
int toadd = 0;
for(i=0; i< n;++i)
{
if((i < s) || (i > e))
{
toadd = a[i];
}
if(i >=s && i <= e)
{
if(0 == a[i])
toadd = 1;
}
sum+=toadd;
toadd = 0;
}
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;
}
}
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 }
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)
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)
{
System.out.println("Invalid!!Please enter again");
l = in.nextInt();
}
System.out.println("Enter the upper limit");
r = in.nextInt();
while(r > Arr.length-1)
{
System.out.println("Invalid!!Please try again");
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;
}
}
}
}
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)
{
System.out.println("Invalid!!Please enter again");
l = in.nextInt();
}
System.out.println("Enter the upper limit");
r = in.nextInt();
while(r > Arr.length-1)
{
System.out.println("Invalid!!Please try again");
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;
}
}
}
}
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;
}
#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;
}
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
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);
}
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;
}
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;
}
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;
}
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;
}
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)
- thelineofcode January 02, 2014