n th number with two set bits n ranging from 1 to 10^14

Question

Look at the following sequence: 3, 5, 6, 9, 10, 12, 17, 18, 20....

All the numbers in the series has exactly 2 bits set in their binary representation. Your task is simple, you have to find the Nth number of this sequence. For each test case, print the Nth number of the sequence, separated by newline. Since the number can be very large, print number % 1000000007.

I am unable to figure out why it is failing for some test cases, and will my code work for the specified range.

Here is my code snippet:

public class Solution {
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner scan=new Scanner(System.in);
        int t = scan.nextInt();
        for(int j=0 ; j<t ; j++){
            long n=scan.nextInt();
            long r = 0;
            long i = 1;
            while((r = i*(i+1)/2) < n)
            {
                i++;
            }
            long res = (1<<i) + (1 << (i-(r-n)-1));
            System.out.println(res);
        }
    }
}

Please give details, this is unclear, clarify the title and the post — azro, Oct 07 '18 at 15:33
Which test cases are failing, what you are actually expect from your code, initial input data and expected output? — Maxim, Oct 07 '18 at 15:41
No, you have not given an example of when it fails and what the result was vs the expected output. — Joakim Danielson, Oct 07 '18 at 16:36

RubenDG · Answer 1 · 2018-10-09T20:08:35.877

It's a sequence, so you could look on the right encyclopedia, OEIS - Sum of two distinct powers of 2, to find every info you need.
You'll find algorithms too. Here's a Java translation of one of them.

for (int j = 0; j < t; j++) {
    long n = scan.nextInt();
    if (n < 1954) {
        nthLongTwoBitSets(n);
    } else {
        nthBigIntegerTwoBitSets(n);
    }
}

r and i are the index of the two set bits.
If you have to multiply or divide for a power of 2, you can use the the bit shift operators to speed things up.
Once the number became to big for a long, you have to use a BigInteger

Edit: Since "print number % 1000000007", you have to declare the following variable in your class
private static final BigInteger MOD = new BigInteger("1000000007");
Then we're going to use the module operator.

public static void nthLongTwoBitSets(long n) {
    long r = ((long) Math.sqrt((n << 3) - 1) + 1) >>> 1;
    long i = n - ((r * (r - 1)) >>> 1) - 1;
    long result = (1L << r) | (1L << i);
    result %= 1000000007;
    System.out.println(result);
}

public static void nthBigIntegerTwoBitSets(long n) {
    int r = ((int) Math.sqrt((n << 3) - 1) + 1) >>> 1;
    int i = (int) n - ((r * (r - 1)) >>> 1) - 1;
    BigInteger result = BigInteger.ZERO.setBit(r).setBit(i).mod(MOD);
    System.out.println(result.toString());
}

Edit2: I cannot access to that link, but if the runtime error is due to a timeout, we have to do some micro-optimization (which are a bad practice in almost every case), so 1) no more BigInteger and 2) only one System.out.println because it's very expensive. We're going to store the string in a StringBuilder

public class Solution {

    private final static long MOD = 1000000007L;
    private final static long FIXED = 46480318; // (1L << 42) % mod;

    public static void main(String[] args) {

        String sep = "\n";
        StringBuilder sb = new StringBuilder(90000);
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        for(int j=0 ; j<t ; j++){
            long n = scan.nextInt();
            sb.append(nthLongTwoBitSets(n));
            sb.append(sep);
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }

    public static long nthLongTwoBitSets2(final long n) {
        long r = ((long) Math.sqrt((n << 3) - 1) + 1) >>> 1;
        long i = n - ((r * (r - 1)) >>> 1) - 1;
        long rMod = 1;
        while (r > 62) {
            r -= 42;
            rMod *= FIXED;
            rMod %= MOD;
        }
        rMod *= (1L << r);
        rMod %= MOD;
        long iMod = 1;
        while (i > 62) {
            i -= 42;
            iMod *= FIXED;
            iMod %= MOD;
        }
        iMod *= (1L << i);
        iMod %= MOD;
        final long result = (rMod + iMod) % MOD;

        return result;
    }
}

thanks for the solution ....but still i am getting wrong answer and run time error for some test cases... — prem kumar, Oct 07 '18 at 17:56
@premkumar could you please provide a link to exercise's statement or update your question copy-pasting it (the whole statement)? — RubenDG, Oct 07 '18 at 18:35
@premkumar Try now. I updated the answer changing the arithmetic shift right to [logical shift right](https://stackoverflow.com/a/2811372/8682068) — RubenDG, Oct 07 '18 at 19:34
still its failing ... I updated my question...once check it if there might be any clue.... and stil i am getting runtime error for one testcase — prem kumar, Oct 08 '18 at 17:07
@premkumar "print number % 1000000007". For future reference, please do not hide requirements and constraints. I updated the answer. — RubenDG, Oct 08 '18 at 18:31
@premkumar Could you provide either more info about the error or the link to the test? — RubenDG, Oct 09 '18 at 17:35
https://www.hackerrank.com/contests/smart-interviews/challenges/si-two-set-bits ...here is the link.. — prem kumar, Oct 09 '18 at 17:40
@premkumar Thanks, but I cannot access it :( I updated the answer hoping the error's cause is a timeout. — RubenDG, Oct 09 '18 at 20:10

n th number with two set bits n ranging from 1 to 10^14

1 Answers1