initialize array with 0 and provide appropriate value to c otherwise
it will be negative and
here c is using as index for array.
procedure visit(node root,int s[],int c) {
if (root= null)
return 0;
S[c] += n.value;
visit(root->left, c - 1)
visit(root->right, c + 1)
}
On Fri,
yea i know 1st Approach is much better and is Only O(N^2) for
precomputing all the values for nck and then O(k) for finding no of
bits set in The Kth number and another loop of O(k) to find the
required number
i posted 2nd approach in the context to vandana's tree approach of
sorting 2^N numbers,
procedure visit(node root,int c) {
if (root= null)
return 0;
S[c] += n.value;
visit(root->left, c - 1)
visit(root->right, c + 1)
}
On Fri, Oct 21, 2011 at 1:22 PM, Mohak Naik wrote:
> If we want to compute the sum of every column, we can use the following
> algorithm
>
> a
@Aamir: Something like this might work:
n %= p;
m %= p;
result = 0;
while( m )
{
if( m & 1 )
{
result += n;
if( result >= p )
result -= p;
}
m >>= 1;
n <<= 1;
if( n >= p )
n -= p;
}
What this does is similar to the elementary school meth
If we want to compute the sum of every column, we can use the following
algorithm
procedure visit(node n, int c) {
if (n.left != null)
S{c} += n.value;
visit(n.left, c - 1)
visit(n.right, c + 1)
}
and call once visit(A, 0), where A is the root node. Note that S{...} in the
algorithm
Use NTL's ZZ extended integer type.
Don
On Oct 21, 12:26 pm, Aamir Khan wrote:
> Lets say n,m and p are three long long integers.
>
> i want to calculate (n*m)%p.
>
> If (n*m) overflows the limit of long long then the answer would be wrong.
> Moreover if i do ((n%p)*(m%p))%p then also there is no
Lets say n,m and p are three long long integers.
i want to calculate (n*m)%p.
If (n*m) overflows the limit of long long then the answer would be wrong.
Moreover if i do ((n%p)*(m%p))%p then also there is no certainty of getting
correct answer.
How should i do this in C++ ?
--
Aamir Khan | 3rd
@Sunny.. why do we need an O(2^N) complexity?
for a value of N=40-50, the solution is not useful..
but, your 1st approach is lot better and i have got it too..
1. O(N) complexity to search the k. (k bits in the numbers) x- (sigma 1->k
(n C i))
2. again, keep substracting (k-i) for i= 0->k-1
