## AN

BAN USERFinal Year Student

- 0of 0 votes

AnswersSuppose two arrays are given A and B. A consists of integers and the second one consists of 0 and 1.

- AN in India

Now a operation is given - You can choose any adjacent bits in array B and you can toggle these two bits ( for example - 00->11, 01->10, 10->01, 11->00) and you can perform this operation any number of times.

The output should be the sum of A[0]*B[0]+A[1]*B[1]+....+A[N-1]*B[N-1] such that the sum is maximum

During the interview, my approach to this problem was to get the maximum number of 1's in array B in order to maximize the sum.

So to do that , I first calculated the total number of 1's in O(n) time in B. Let count = No. Of 1's=x

Then I started traversing the array and toggle only if count becomes greater than x or based on the elements of array A(for example : Let B[i]=0 and B[i+1]=1 & A[i]=51 and A[i+1]=50

So I will toggle B[i] B[i+1] because A[i]>A[i+1])

But the interviewer was not quite satisfied with my approach and was asking me further to develop a less time complex algorithm.

Can anyone suggest a better approach with lesser time complexity??| Report Duplicate | Flag | PURGE

Software Developer Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window