Mohamed.Gaber86
BAN USERYou can keep a variable contains summation of ( Ai - Bi ); once this variable becomes negative then you set the k with the following index
note: there is always solution for this problem as long as sum(A) = sum(B)
int getKIndex ( int a[], int b[], int N)
{
int s = 0 ; int k = 0 ;
for ( int i = 0 ; i < N ; i++)
{
s += a[i] - b[i] ;
if ( s < 0 )
{
s = 0;
k = ( i + 1 ) % N ;
}
}
return k ;
}
Code is correct only if n = pow ( 2, i) - 1
if n == 4 for example
list will be,
001
010
011
100
Xoring will not work in the case, the last bit occurances is 1
One solution is :-
display the tree in order, then search fro successor. requires O(n) space, O(n) time.
what if the most left node is equal to g value , tree may have duplicates.
- Mohamed.Gaber86 January 16, 2013
We can count number of ones in the given number using bit masking , say N ones, then we can count the numbers with same popcount with simple combination ( choose N bites from the 32 bit )
- Mohamed.Gaber86 March 04, 2013int N = 0 ;
for ( i = 0 ; i < 32 ; i++ )
{
if ( number & ( 1 << i ) != 0 )
N++ ;
}
return C(32, N) = 32! / ( N! * ( 32-N)! )