Given an integer N, the task is to find the Nth natural number with exactly two bits set.
Examples:
Input: N = 4
Output: 9
Explanation:
Numbers with exactly two bits set: 3, 5, 6, 9, 10, 12, …
4th number in this is 9
Input: N = 15
Output: 48
Naive Approach:
- Run a loop through all natural numbers, and for each number, check if it has two bits set or not by counting set bits in a number.
- Print the Nth number having two set bits.
Efficient Approach:
- Find the leftmost set bit by finding the partition to which N belongs (Partition ‘i’ has ‘i’ numbers in it).
- To find the other set bit, we’ll have to first find the distance of N from the last number of the previous partition. Based on their difference, we set the corresponding bit.
k = k | (1<<(i))
- Below is the implementation of the above approach:
C++
// C++ Code to find the Nth number// with exactly two bits set#include <bits/stdc++.h>using namespace std;// Function to find the Nth number// with exactly two bits setvoid findNthNum(long long int N){ long long int bit_L = 1, last_num = 0; // Keep incrementing until // we reach the partition of 'N' // stored in bit_L while (bit_L * (bit_L + 1) / 2 < N) { last_num = last_num + bit_L; bit_L++; } // set the rightmost bit // based on bit_R int bit_R = N - last_num - 1; cout << (1 << bit_L) + (1 << bit_R) << endl;}// Driver codeint main(){ long long int N = 13; findNthNum(N); return 0;} |
Java
// Java Code to find the Nth number// with exactly two bits setclass GFG{ // Function to find the Nth number// with exactly two bits setstatic void findNthNum(int N){ int bit_L = 1, last_num = 0; // Keep incrementing until // we reach the partition of 'N' // stored in bit_L while (bit_L * (bit_L + 1) / 2 < N) { last_num = last_num + bit_L; bit_L++; } // set the rightmost bit // based on bit_R int bit_R = N - last_num - 1; System.out.print((1 << bit_L) + (1 << bit_R) +"\n");} // Driver codepublic static void main(String[] args){ int N = 13; findNthNum(N);}}// This code is contributed by Princi Singh |
Python3
# Python Code to find the Nth number# with exactly two bits set# Function to find the Nth number# with exactly two bits setdef findNthNum(N): bit_L = 1; last_num = 0; # Keep incrementing until # we reach the partition of 'N' # stored in bit_L while (bit_L * (bit_L + 1) / 2 < N): last_num = last_num + bit_L; bit_L+=1; # set the rightmost bit # based on bit_R bit_R = N - last_num - 1; print((1 << bit_L) + (1 << bit_R));# Driver codeif __name__ == '__main__': N = 13; findNthNum(N);# This code contributed by PrinciRaj1992 |
C#
// C# Code to find the Nth number// with exactly two bits setusing System;class GFG{ // Function to find the Nth number// with exactly two bits setstatic void findNthNum(int N){ int bit_L = 1, last_num = 0; // Keep incrementing until // we reach the partition of 'N' // stored in bit_L while (bit_L * (bit_L + 1) / 2 < N) { last_num = last_num + bit_L; bit_L++; } // set the rightmost bit // based on bit_R int bit_R = N - last_num - 1; Console.Write((1 << bit_L) + (1 << bit_R) +"\n");} // Driver codepublic static void Main(String[] args){ int N = 13; findNthNum(N);}}// This code is contributed by Princi Singh |
Javascript
<script>// JavaScript Code to find the Nth number// with exactly two bits set// Function to find the Nth number// with exactly two bits setfunction findNthNum(N){ let bit_L = 1, last_num = 0; // Keep incrementing until // we reach the partition of 'N' // stored in bit_L while (bit_L * (bit_L + 1) / 2 < N) { last_num = last_num + bit_L; bit_L++; } // set the rightmost bit // based on bit_R let bit_R = N - last_num - 1; document.write((1 << bit_L) + (1 << bit_R) + "<br>");}// Driver codelet N = 13;findNthNum(N);// This code is contributed by Mayank Tyagi</script> |
Output:
36
Time Complexity : O(Partition of Number)
Auxiliary space: O(1) as it is using constant variables
