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 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.
- 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 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)=?
- 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.
- 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
That's all for this topic. If you guys have any suggestions or queries, feel free to drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here.
Happy Learning 🙂
If you like the content on CodePumpkin and if you wish to do something for the community and the planet Earth, you can donate to our campaign for planting more trees at CodePumpkin Cauvery Calling Campaign.
We may not get time to plant a tree, but we can definitely donate ₹42 per Tree.
About the Author
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.
