code::
#include <stdio.h>
#include<conio.h>
void check(int &count, int &k,int max)
{
int right,leftmost,rightmost;
if(k==1)
return;
right=count&(-count);
leftmost=count+right;
rightmost=count^leftmost;
rightmost=rightmost/right;
rightmost=rightmost>>2;
count=leftmost|rightmost;
if(count>=max)
return;
k=k-1;
check(count,k,max);
}
void func(int n,int k)
{
int count =1,j,max;
if(k==1)
printf("%d\n",0);
else
{
k=k-1;
for(int i=1;i<=n;i++)
{
count=1;
j=1;
max=1<<n;
while(j!=i)
{ count=(count<<1)+1;
j++;
}
check(count,k,max);
if(k==1)
{ printf("%d\n",count);
break;
}
else
k=k-1;
}
}
}
int main()
{
func(7,127);//left for N>0 and and right for K..chech for any other
values....
getch();
return 0;
}
Tell me .. if u find any test cases failed...Thankx...
With regards,
Praveen Raj
DCE-IT 3rd yr
9999735993
[email protected]
On Wed, Oct 26, 2011 at 1:56 PM, praveen raj <[email protected]> wrote:
> made it.. :)
>
> With regards,
>
> Praveen Raj
> DCE-IT 3rd yr
> 9999735993
> [email protected]
>
>
>
>
> On Tue, Oct 25, 2011 at 11:13 AM, raju <[email protected]> wrote:
>
>> @icy
>> It's still there except that you'll get a different question.
>> That page promises you a telephone interview if you solve the challenge
>> but I don't know how true that is for non-US guys ..
>> i solved one question two weeks back .. and no one contacted me till now
>> ..
>>
>> ~raju
>>
>>
>> On Tue, Oct 25, 2011 at 3:27 AM, icy` <[email protected]> wrote:
>>
>>> is this contest still going? if so, where ? i have a solution that
>>> does
>>> (100, 1267650600228229401496703205376 ) (just one hundred 1's)
>>> in 0.03 seconds in an older ruby on an older pc
>>>
>>> I'd like to submit ;P
>>>
>>>
>>> On Oct 21, 10:48 pm, sunny agrawal <[email protected]> wrote:
>>> > 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, rather simply sort the numbers in the array...
>>> > and this approach is O(N*2^N)
>>> >
>>> > On 10/21/11, sravanreddy001 <[email protected]> wrote:
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> > > @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 so.. O(k) here
>>> > > and recursively performing step 2. (worst case complexity is O(T))
>>> > > where T = nCk
>>> >
>>> > > O(N) + O(T) ==> O(T) as it dominates the given number. unless it
>>> doesn't
>>> > > fall in the range.. or equivalently --> max( O(T), O(N) )
>>> >
>>> > > --
>>> > > You received this message because you are subscribed to the Google
>>> Groups
>>> > > "Algorithm Geeks" group.
>>> > > To view this discussion on the web visit
>>> > >https://groups.google.com/d/msg/algogeeks/-/NJR9l-UB7c8J.
>>> > > To post to this group, send email to [email protected].
>>> > > To unsubscribe from this group, send email to
>>> > > [email protected].
>>> > > For more options, visit this group at
>>> > >http://groups.google.com/group/algogeeks?hl=en.
>>> >
>>> > --
>>> > Sunny Aggrawal
>>> > B.Tech. V year,CSI
>>> > Indian Institute Of Technology,Roorkee
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected].
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
