Program to find nth digit of the series 3, 5, 6, 9, 10, 12, …
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 n^{th} digit of this series?
We have to write a program or a function which will give me the n^{th} digit of this series.
f(n) = n^{th} 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.
- 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.
- left most bit in each number is always one.
- one set bit will traverse from right most bit to 2^{nd} left most bit in each partition.
Based on this observations, how we will get n^{th} bit of our series. Let's understand this by an example, for n = 12, f(n)=?
- n=12 is a part of 5^{th} partition i.e. i=5. Also left most bit is 5^{th} bit. So we can say that left most bit will be i^{th} bit i.e. 2^{5} =^{ }32.
- Now we need to find pattern for 2^{nd} 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) = 2^{5} + 2^{1}
= 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
Tags: Bit Manipulation, Bitwise Operators
Comments and Queries
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>For more information on supported HTML tags in disqus comment, click here.