CODEWITHSUNDEEP
javaalgorithmmathsequence
yahh
yahh

Reputation: 1195

check number present in a sequences

I am writing a program which I found on a coding competition website, I have sort of figured out how to solve the problem but, I am stuck on a math part of it, I am completely diluting the problem and showing what I need.

first I need to check if a number is part of a sequence, my sequence is 2*a+1 where a is the previous element in the sequence or 2^n-1 to get nth item in the sequence. so it is 1,3,7,15,31,63...

I don't really want to create the whole sequence and check if a number is present, but I am not sure what a quicker method to do this would be.

Second if I am given a number lets say 25, I want to figure out the next highest number in my sequence to this number. So for 25 it would be 31 and for 47 it would be 63, for 8 it would be 13.

How can i do these things without creating the whole sequence.

I have seen similar questions here with different sequences but I am still not sure how to solve this

Upvotes: 0

Views: 2596

Answers (3)

WoooHaaaa
WoooHaaaa

Reputation: 20450

How to find the next higher number :

For example, we get 19 ( 10011 ) , should return 31 (11111)

int findNext(int n){
    if(n == 0) return 1;

    int ret = 2;         // start from 10
    while( (n>>1) > 0){  // end with 100000
        ret<<1;
    }
    return ret-1;
}

Upvotes: 0

Blender
Blender

Reputation: 298146

Start by finding the explicit formula for any term in your sequence. I'm too lazy to write out a proof, so just add 1 to each term in your sequence:

 1 + 1 =  2
 3 + 1 =  4
 7 + 1 =  8
15 + 1 = 16
31 + 1 = 32
63 + 1 = 64
...

You can clearly see that a_n = 2^n - 1.

To check if a particular number is in your sequence, assume that it is:

x = 2^n - 1
x + 1 = 2^n

From Wikipedia:

The binary representation of integers makes it possible to apply a very fast test to determine whether a given positive integer x is a power of two:

positive x is a power of two ⇔ (x & (x − 1)) equals to zero.

So to check, just do:

bool in_sequence(int n) {
    return ((n + 1) & n) == 0;
}

Upvotes: 2

Alvin Wong
Alvin Wong

Reputation: 12420

As @Blender already pointed out your sequence is essentially 2^n - 1, you can use this trick if you use integer format to store it:

boolean inSequence(int value) {
    for (int i = 0x7FFF; i != 0; i >>>= 1) {
        if (value == i) {
            return true;
        }
    }
    return false;
}

Note that for every elements in your sequence, its binary representation will be lots of 0s and then lots of 1s.

For example, 7 in binary is 0000000000000000000000000000111 and 63 in binary is 0000000000000000000000000111111.

This solution starts from 01111111111111111111111111111111 and use an unsigned bitshift, then compare if it is equal to your value.

Nice and simple.

Upvotes: 1

Related Questions