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.
Solution :
a simple way to explain this would be to consider this as a switch.
0 - OFF state
1 - ON state
01 - switch going from OFF to ON.
10 - switch going from ON to OFF.
If the 1st and last element are the same then that means that the switch has been toggled even no. of times. Hence no. of 01's and 10's are equal.
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.
Solution :
a simple way to explain this would be to consider this as a switch.
0 - OFF state
1 - ON state
01 - switch going from OFF to ON.
10 - switch going from ON to OFF.
If the 1st and last element are the same then that means that the switch has been toggled even no. of times. Hence no. of 01's and 10's are equal.
No comments:
Post a Comment