# Program to find nth digit of the series 3, 5, 6, 9, 10, 12, …

August 20, 2017
Posted by Pumpkin

Bit Manipulation programming questions are integral part of any online coding challenges or programming rounds of 3-4 year exp Java/C/Python developer interviews.

So, why are we talking about bit manipulation in this series problem? Lets look at the binary representation of all the numbers in this series.

Decimal Digit Binary Representation
3 0011
5 0101
6 0110
9 1001
10 1010
12 1100

If you notice the number of set bits in each digit, you will find that each digit contains only two set bits. So, what is the next number in the series?

well, its 17 (10001) because  13 (1101) and 14 (1110) contains three set bits,  15 (1111) contains four set bits and 16 (10000) contains only one set bit.

## How do we find nth digit of this series?

We have to write a program or a function which will give me the nth digit of this series.

f(n) = nth digit of the series

So, f(1) = 3, f(2)=5, f(3)=6 and so on.

To solve such problem, we should write initial numbers of the series and try to find some pattern.  Let's write down first 15 digit of our series and its binary representation.

Notice the pattern in each binary number.

1. We can divide this numbers in the partition of 1,2,3,4,5 and so on. We have used 'i' to denote each partition.
2. left most bit in each number is always one.
3. one set bit will traverse from right most bit to 2nd left most bit in each partition.

Based on this observations, how we will get nth bit of our series. Let's understand this by an example, for n = 12, f(n)=?

1. n=12 is a part of 5th partition i.e. i=5. Also left most bit is 5th bit. So we can say that left most bit will be ith bit  i.e. 25 = 32.
2. Now we need to find pattern for 2nd set bit. We can use below formula to find the second set bit

i – (r-n) -1      where    i = partition number,  r = maximum number in the partition,  n = input number

For n =12,

i = 5,                       // We can find i by iterating through the loop as shown in below java program

r = i * (i+1) / 2     // Formula for 1+2+3+4+5+ …

= 5 * 6 / 2

r = 15

So, 2nd set bit = i – (r-n) – 1

= 5 – (15-12) -1

= 1

Hence, f(12) = 25 + 21

= 32 + 2

= 34

Java Program Implementation

```
public class NumbeSeriesWithTwoOnes {

public static void main(String[] args) {
getNumber(12);
}

public static int getNumber(int n)
{
int r = 0;
int i = 1;
while((r=i*(i+1)/2)<n)
{
i++;
}
System.out.println("f(" + n + ") = " +(int)(Math.pow(2, i) + Math.pow(2, i-(r-n)-1)));
return n;
}
}```

Output:

```
f(12) = 34```

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
```<pre><code class="java">
String foo = "bar";
</code></pre>
```