Given a number n, print first n positive integers with exactly two set bits in their binary representation.
Examples :
Input: n = 3 Output: 3 5 6 The first 3 numbers with two set bits are 3 (0011), 5 (0101) and 6 (0110) Input: n = 5 Output: 3 5 6 9 10 12
A Simple Solution is to consider all positive integers one by one starting from 1. For every number, check if it has exactly two sets bits. If a number has exactly two set bits, print it and increment count of such numbers.
An Efficient Solution is to directly generate such numbers. If we clearly observe the numbers, we can rewrite them as given below pow(2,1)+pow(2,0), pow(2,2)+pow(2,0), pow(2,2)+pow(2,1), pow(2,3)+pow(2,0), pow(2,3)+pow(2,1), pow(2,3)+pow(2,2), ………
All numbers can be generated in increasing order according to higher of two set bits. The idea is to fix higher of two bits one by one. For current higher set bit, consider all lower bits and print the formed numbers.
C++
// C++ program to print first n numbers// with exactly two set bits#include <iostream>using namespace std;// Prints first n numbers with two set bitsvoid printTwoSetBitNums(int n){ // Initialize higher of two sets bits int x = 1; // Keep reducing n for every number // with two set bits. while (n > 0) { // Consider all lower set bits for // current higher set bit int y = 0; while (y < x) { // Print current number cout << (1 << x) + (1 << y) << " "; // If we have found n numbers n--; if (n == 0) return; // Consider next lower bit for current // higher bit. y++; } // Increment higher set bit x++; }}// Driver codeint main(){ printTwoSetBitNums(4); return 0;} |
Java
// Java program to print first n numbers// with exactly two set bitsimport java.io.*;class GFG { // Function to print first n numbers with two set bits static void printTwoSetBitNums(int n) { // Initialize higher of two sets bits int x = 1; // Keep reducing n for every number // with two set bits while (n > 0) { // Consider all lower set bits for // current higher set bit int y = 0; while (y < x) { // Print current number System.out.print(((1 << x) + (1 << y)) +" "); // If we have found n numbers n--; if (n == 0) return; // Consider next lower bit for current // higher bit. y++; } // Increment higher set bit x++; } } // Driver program public static void main (String[] args) { int n = 4; printTwoSetBitNums(n); }}// This code is contributed by Pramod Kumar |
Python3
# Python3 program to print first n # numbers with exactly two set bits # Prints first n numbers # with two set bits def printTwoSetBitNums(n) : # Initialize higher of # two sets bits x = 1 # Keep reducing n for every # number with two set bits. while (n > 0) : # Consider all lower set bits # for current higher set bit y = 0 while (y < x) : # Print current number print((1 << x) + (1 << y), end = " " ) # If we have found n numbers n -= 1 if (n == 0) : return # Consider next lower bit # for current higher bit. y += 1 # Increment higher set bit x += 1 # Driver code printTwoSetBitNums(4) # This code is contributed # by Smitha |
C#
// C# program to print first n numbers// with exactly two set bitsusing System;class GFG { // Function to print first n // numbers with two set bits static void printTwoSetBitNums(int n) { // Initialize higher of // two sets bits int x = 1; // Keep reducing n for every // number with two set bits while (n > 0) { // Consider all lower set bits // for current higher set bit int y = 0; while (y < x) { // Print current number Console.Write(((1 << x) + (1 << y)) +" "); // If we have found n numbers n--; if (n == 0) return; // Consider next lower bit // for current higher bit. y++; } // Increment higher set bit x++; } } // Driver program public static void Main() { int n = 4; printTwoSetBitNums(n); }} // This code is contributed by Anant Agarwal. |
PHP
<?php// PHP program to print // first n numbers with // exactly two set bits// Prints first n numbers // with two set bitsfunction printTwoSetBitNums($n){ // Initialize higher of // two sets bits $x = 1; // Keep reducing n for // every number with // two set bits. while ($n > 0) { // Consider all lower set // bits for current higher // set bit $y = 0; while ($y < $x) { // Print current number echo (1 << $x) + (1 << $y), " "; // If we have found n numbers $n--; if ($n == 0) return; // Consider next lower // bit for current // higher bit. $y++; } // Increment higher set bit $x++; }}// Driver codeprintTwoSetBitNums(4);// This code is contributed by Ajit?> |
Javascript
<script>// Javascript program to print first n numbers// with exactly two set bits// Prints first n numbers with two set bitsfunction printTwoSetBitNums(n){ // Initialize higher of two sets bits let x = 1; // Keep reducing n for every number // with two set bits. while (n > 0) { // Consider all lower set bits for // current higher set bit let y = 0; while (y < x) { // Print current number document.write((1 << x) + (1 << y) + " "); // If we have found n numbers n--; if (n == 0) return; // Consider next lower bit for current // higher bit. y++; } // Increment higher set bit x++; }}// Driver codeprintTwoSetBitNums(4);// This code is contributed by Mayank Tyagi</script> |
Output :
3 5 6 9
Time Complexity : O(n)
Auxiliary Space: O(1)
This article is contributed by Bharath Reddy Appareddy. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Approach#2: Using while and join
The approach is to start from the integer 3 and check whether the number of set bits in its binary representation is equal to 2 or not. If it has exactly 2 set bits, then add it to the list of numbers with 2 set bits until the list has n elements.
Algorithm
1. Initialize an empty list res to store the integers with exactly two set bits.
2. Initialize an integer variable i to 3.
3. While the length of the list res is less than n, do the following:
a. Check whether the number of set bits in the binary representation of i is equal to 2 or not using the count() method of the string.
b. If the number of set bits is equal to 2, then append i to the list res.
c. Increment i by 1.
4. Return the list res.
Python3
def numbersWithTwoSetBits(n): res = [] i = 3 while len(res) < n: if bin(i).count('1') == 2: res.append(i) i += 1 return resn = 3result = numbersWithTwoSetBits(n)output_string = ' '.join(str(x) for x in result)print(output_string) |
3 5 6
Time Complexity: O(n log n), where n is the number of integers with exactly two set bits. This is because we are checking the number of set bits in the binary representation of each integer, which takes O(log n) time.
Space Complexity: O(n), where n is the number of integers with exactly two set bits. This is because we are storing the list of integers with two set bits in memory.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
