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