Code Pumpkin

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

August 20, 2017
Posted by Pumpkin
Subscribe

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 nthdigit 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.

Series Of Two Set bits

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 nthbit 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 5thbit. 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

That's all for this topic. If you guys can think of any more similar java programs, feel free 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 🙂

Tags: ,


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.

Total Post : 80
Subscribe
Contribute Your Articles

Interview Experiences

Related Books

Like Us On Facebook

Alexa Page Rank