Выведите первые n чисел ровно с двумя заданными битами
Учитывая число n, выведите первые n натуральных чисел с ровно двумя заданными битами в их двоичном представлении.
Примеры :
Ввод: n = 3 Вывод: 3 5 6 Первые 3 числа с двумя установленными битами - 3 (0011), 5 (0101) и 6 (0110) Ввод: n = 5 Выход: 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 bits 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 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 code int main() { printTwoSetBitNums(4); return 0; } |
Java
// Java program to print first n numbers // with exactly two set bits import 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 bits using 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 bits function 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 code printTwoSetBitNums(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 bits function 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 code printTwoSetBitNums(4); // This code is contributed by Mayank Tyagi </script> |
Выход :
3 5 6 9
Сложность времени: O (n)
Эта статья предоставлена Bharath Reddy Appareddy . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.