# Program to find the Nth natural number with exactly two bits set | Set 2

Given an integer **N**, the task is to find the **N ^{th}** natural number with exactly two set bits.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:N = 4Output:9Explanation:Numbers with exactly two set bits are 3, 5, 6, 9, 10, 12, ….

The 4^{th}term in this series is 9.

Input:N = 15Output:48Explanation:Numbers with exactly two set bits are 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48….

The 15^{th}term in this series is 48.

**Naive Approach:** Refer to the previous post of this article for the simplest solution possible for this problem.

**Time Complexity:** O(N)**Auxiliary Space:** O(1)

**Efficient Approach:** To optimize the above approach, the idea to use Binary Search to find the **N ^{th} number**. Follow the steps below to solve the problem:

- Any number in the given series is in the form
**(2**where^{a}+ 2^{b})**a > b**. - The
**N**in a series can be identified by identifying values^{th}term**a**and**b**. - Find the value of
**a**such that**(a * (a + 1)) / 2 ≥ N**and keeping a constraint that**a**must be minimum - Therefore, find the value of
**a**for constraints in the above steps using Binary Search. - After the above steps, find the value of
**b**using**a**and**N**and print the result as**(2**.^{a}+ 2^{b})

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find the Nth number` `// with exactly two bits set` `void` `findNthNum(` `long` `long` `int` `N)` `{` ` ` `// Initialize variables` ` ` `long` `long` `int` `a, b, left;` ` ` `long` `long` `int` `right, mid;` ` ` `long` `long` `int` `t, last_num = 0;` ` ` `// Initialize the range in which` ` ` `// the value of 'a' is present` ` ` `left = 1, right = N;` ` ` `// Perform Binary Search` ` ` `while` `(left <= right) {` ` ` `// Find the mid value` ` ` `mid = left + (right - left) / 2;` ` ` `t = (mid * (mid + 1)) / 2;` ` ` `// Update the range using the` ` ` `// mid value t` ` ` `if` `(t < N) {` ` ` `left = mid + 1;` ` ` `}` ` ` `else` `if` `(t == N) {` ` ` `a = mid;` ` ` `break` `;` ` ` `}` ` ` `else` `{` ` ` `a = mid;` ` ` `right = mid - 1;` ` ` `}` ` ` `}` ` ` `// Find b value using a and N` ` ` `t = a - 1;` ` ` `b = N - (t * (t + 1)) / 2 - 1;` ` ` `// Print the value 2^a + 2^b` ` ` `cout << (1 << a) + (1 << b);` `}` `// Driver Code` `int` `main()` `{` ` ` `long` `long` `int` `N = 15;` ` ` `// Function Call` ` ` `findNthNum(N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG{` `// Function to find the Nth number` `// with exactly two bits set` `static` `void` `findNthNum(` `int` `N)` `{` ` ` `// Initialize variables` ` ` `int` `a = ` `0` `, b, left;` ` ` `int` `right, mid;` ` ` `int` `t, last_num = ` `0` `;` ` ` `// Initialize the range in which` ` ` `// the value of 'a' is present` ` ` `left = ` `1` `;` ` ` `right = N;` ` ` `// Perform Binary Search` ` ` `while` `(left <= right) {` ` ` `// Find the mid value` ` ` `mid = left + (right - left) / ` `2` `;` ` ` `t = (mid * (mid + ` `1` `)) / ` `2` `;` ` ` `// Update the range using the` ` ` `// mid value t` ` ` `if` `(t < N) {` ` ` `left = mid + ` `1` `;` ` ` `}` ` ` `else` `if` `(t == N) {` ` ` `a = mid;` ` ` `break` `;` ` ` `}` ` ` `else` `{` ` ` `a = mid;` ` ` `right = mid - ` `1` `;` ` ` `}` ` ` `}` ` ` `// Find b value using a and N` ` ` `t = a - ` `1` `;` ` ` `b = N - (t * (t + ` `1` `)) / ` `2` `- ` `1` `;` ` ` `// Print the value 2^a + 2^b` ` ` `System.out.print((` `1` `<< a) + (` `1` `<< b));` `}` `// Driver Code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `N = ` `15` `;` ` ` `// Function Call` ` ` `findNthNum(N);` `}` `}` `// This code contributed by shikhasingrajput` |

## Python3

`# Python3 program for the above approach` `# Function to find the Nth number` `# with exactly two bits set` `def` `findNthNum(N):` ` ` ` ` `# Initialize variables` ` ` `last_num ` `=` `0` ` ` `# Initialize the range in which` ` ` `# the value of 'a' is present` ` ` `left ` `=` `1` ` ` `right ` `=` `N` ` ` `# Perform Binary Search` ` ` `while` `(left <` `=` `right):` ` ` ` ` `# Find the mid value` ` ` `mid ` `=` `left ` `+` `(right ` `-` `left) ` `/` `/` `2` ` ` `t ` `=` `(mid ` `*` `(mid ` `+` `1` `)) ` `/` `/` `2` ` ` `# Update the range using the` ` ` `# mid value t` ` ` `if` `(t < N):` ` ` `left ` `=` `mid ` `+` `1` ` ` `elif` `(t ` `=` `=` `N):` ` ` `a ` `=` `mid` ` ` `break` ` ` `else` `:` ` ` `a ` `=` `mid` ` ` `right ` `=` `mid ` `-` `1` ` ` `# Find b value using a and N` ` ` `t ` `=` `a ` `-` `1` ` ` `b ` `=` `N ` `-` `(t ` `*` `(t ` `+` `1` `)) ` `/` `/` `2` `-` `1` ` ` `# Print the value 2^a + 2^b` ` ` `print` `((` `1` `<< a) ` `+` `(` `1` `<< b))` `# Driver Code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `N ` `=` `15` ` ` `# Function Call` ` ` `findNthNum(N)` `# This code is contributed by chitranayal` |

## C#

`// C# program for the above approach` `using` `System;` ` ` `class` `GFG{` ` ` `// Function to find the Nth number` `// with exactly two bits set` `static` `void` `findNthNum(` `int` `N)` `{` ` ` ` ` `// Initialize variables` ` ` `int` `a = 0, b, left;` ` ` `int` `right, mid;` ` ` `int` `t;` ` ` `//int last_num = 0;` ` ` ` ` `// Initialize the range in which` ` ` `// the value of 'a' is present` ` ` `left = 1; right = N;` ` ` ` ` `// Perform Binary Search` ` ` `while` `(left <= right)` ` ` `{` ` ` ` ` `// Find the mid value` ` ` `mid = left + (right - left) / 2;` ` ` ` ` `t = (mid * (mid + 1)) / 2;` ` ` ` ` `// Update the range using the` ` ` `// mid value t` ` ` `if` `(t < N)` ` ` `{` ` ` `left = mid + 1;` ` ` `}` ` ` `else` `if` `(t == N)` ` ` `{` ` ` `a = mid;` ` ` `break` `;` ` ` `}` ` ` `else` ` ` `{` ` ` `a = mid;` ` ` `right = mid - 1;` ` ` `}` ` ` `}` ` ` ` ` `// Find b value using a and N` ` ` `t = a - 1;` ` ` `b = N - (t * (t + 1)) / 2 - 1;` ` ` ` ` `// Print the value 2^a + 2^b` ` ` `Console.Write((1 << a) + (1 << b));` `}` ` ` `// Driver Code` `public` `static` `void` `Main()` `{` ` ` `int` `N = 15;` ` ` ` ` `// Function Call` ` ` `findNthNum(N);` `}` `}` `// This code is contributed by sanjoy_62` |

## Javascript

`<script>` `// JavaScript program to implement` `// the above approach` `// Function to find the Nth number` `// with exactly two bits set` `function` `findNthNum(N)` `{` ` ` `// Initialize variables` ` ` `let a = 0, b, left;` ` ` `let right, mid;` ` ` `let t, last_num = 0;` ` ` ` ` `// Initialize the range in which` ` ` `// the value of 'a' is present` ` ` `left = 1;` ` ` `right = N;` ` ` ` ` `// Perform Binary Search` ` ` `while` `(left <= right) {` ` ` ` ` `// Find the mid value` ` ` `mid = left + (right - left) / 2;` ` ` ` ` `t = (mid * (mid + 1)) / 2;` ` ` ` ` `// Update the range using the` ` ` `// mid value t` ` ` `if` `(t < N) {` ` ` `left = mid + 1;` ` ` `}` ` ` `else` `if` `(t == N) {` ` ` `a = mid;` ` ` `break` `;` ` ` `}` ` ` `else` `{` ` ` `a = mid;` ` ` `right = mid - 1;` ` ` `}` ` ` `}` ` ` ` ` `// Find b value using a and N` ` ` `t = a - 1;` ` ` `b = N - (t * (t + 1)) / 2 - 1;` ` ` ` ` `// Print the value 2^a + 2^b` ` ` `document.write((1 << a) + (1 << b));` `}` `// Driver Code` ` ` `let N = 15;` ` ` ` ` `// Function Call` ` ` `findNthNum(N);` ` ` `</script>` |

**Output:**

48

**Time Complexity:** O(log N)**Auxiliary Space:** O(1)