You are given a bit array (i.e each element is 0 or 1) A[1..n].
A bit array is called balanced if the number of times 01 appears is same as the number of times 10 appears. By 01 appearing we mean that A[i] = 0 and A[i+1] = 1 for some i.
i.e.
S1 = { i : A[i] = 0 and A[i+1] = 1}
S2 = {j : A[j] = 1 and A[j+1] = 0}
The array is balanced if number of elements in S1 is same as number of elements in S2.
Eg: A = [1,0,1] is balanced.
A = [0,0,0,0,0,0] is balanced too.
Give an algortihm to determine if a bit array A[1...n] is balanced.
One of solution:
ReplyDeletefor(int i=0;i < (len-1) ; i++){
a[i]-a[i+1] > 0 ? count1++ : count2++;
return count1 == count2;
Best one:
ReplyDeleteJust Compare a[i] == a[n];
First solution fails , we should count no of positives and negatives not zeros.
ReplyDeletedidnt understand second one ,but i think the logic for best solution is : the reverse of that array should be equal to the original one. i can say mirror should be the same. what do u say ?