Given an integer N, the task is to find the Nth natural number with exactly two set bits.
Examples:
Input: N = 4
Output: 9
Explanation: Numbers with exactly two set bits are 3, 5, 6, 9, 10, 12, ….
The 4th term in this series is 9.Input: N = 15
Output: 48
Explanation: Numbers with exactly two set bits are 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48….
The 15th 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 Nth number. Follow the steps below to solve the problem:
- Any number in the given series is in the form (2a + 2b) where a > b.
- The Nth term in a series can be identified by identifying values 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 (2a + 2b).
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 setvoid 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 Codeint main(){ long long int N = 15; // Function Call findNthNum(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the Nth number// with exactly two bits setstatic 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 Codepublic 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 setdef 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 Codeif __name__ == "__main__": N = 15 # Function Call findNthNum(N)# This code is contributed by chitranayal |
C#
// C# program for the above approachusing System; class GFG{ // Function to find the Nth number// with exactly two bits setstatic 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 Codepublic 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 setfunction 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)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
