wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Lucky number
        
(Message started by: harsh487 on Nov 17^th, 2008, 10:34am)

Title: Lucky number
Post by harsh487 on Nov 17^th, 2008, 10:34am

1 2 3 4 5 6 7 8 9 ......and so on

1.Remove every second number
so the now the nos are
1 3 5 7 9 11 13 ......

2.Remove every third number
so now the nos are....
1 3 7 9 13 15 19 .....

3.Remove every fourth number
so now the nos are...
1 3 7 13 15 19 25....

and so on

A number is considered to be lucky if it lies in the list
We are given a number 'n'....we have to check whether the number is lucky or not...

Title: Re: Lucky number
Post by towr on Nov 17^th, 2008, 11:20am

You can find the nth number in O(n) (see http://www.research.att.com/~njas/sequences/A000960). So given F(n), you can find n in O(n log n) using binary search.
Quite possibly it can be done better.

Title: Re: Lucky number
Post by harsh487 on Nov 19^th, 2008, 10:40am

Thanx for the link....Can u explain a little bit more how to search for the number using binary search...the problem is that we can't store the series in an array or something...so how to apply the binary search...The link u gave tells how to find the nth number.....but my question is that we are given a number, suppose 145
...Now we have to tell whether 145 lies in list or not....

Title: Re: Lucky number
Post by towr on Nov 20^th, 2008, 12:50am

on 11/19/08 at 10:40:31, harsh487 wrote:

I'll simulate the process of determining whether 145 is a lucky number.
First we try f(1)=1 which is to small
So next we try f(2)=2, which is still too small
f(4)=13
f(8)=49
f(16)=207, so now this one is too large. If 145 is a lucky number, we must have f(x)=145 with an x between 8 and 16. Try the middle one first.
f(12)=109, which is smaller. So x > 12
f(14)=147, which is too great again, so try a small x
f(13)=133, which is too small. But there is no integer x between 13 and 14 left, so 145 can't be a lucky number.

Note that every f(N) can be calculated in O(N) time; we don't need to have a list of them beforehand.
So we just find the first f(2^m) greater than the number we're looking for, and then do a regular binary search to find whether there's an x between 2^m-1 and 2^m such that f(x) is the number we want.

Title: Re: Lucky number
Post by towr on Nov 20^th, 2008, 2:23am

Here's some c++ code that seems to work.

Code:

int nth_lucky(int n)
{
for(int i=n-1; i>0; i--)
n = (n/i + (n % i > 0) + 1) * i;
return n;
}

bool is_lucky(int n)
{
int m=1, i=1, nl;

while( (nl=nth_lucky(m)) < n && i++ < 8*sizeof(m) )
m <<= 1;

if(n == nl) return true;

int l = m>>1, r = m;
while( l+1 < r)
{
m=(r+l)/2;
nl=nth_lucky(m);
if(n == nl) return true;
else if(n < nl) r=m;
else l=m;
}
return false;
}

Title: Re: Lucky number
Post by Hippo on Nov 20^th, 2008, 5:53am

on 11/20/08 at 02:23:57, towr wrote:

Here's some c++ code that seems to work.

Code:

I would prefere to use font where l and 1 can be distinguished ... :)

Title: Re: Lucky number
Post by towr on Nov 20^th, 2008, 6:55am

on 11/20/08 at 05:53:35, Hippo wrote:

I would prefere to use font where l and 1 can be distinguished ... :)

Yeah, but not much to be done about that, I'm afraid.

Here's a simpler and faster replacement for the second function.

Code:

bool is_lucky(int n)
{
return nth_lucky(static_cast<int>(round(sqrt(n*pi/4)))) == n;
}

Works, as far as I've tested it. Runs in about O(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifn), a factor log(n) better.