Виведіть перші n чисел із рівно двома розрядами
Задано число n. Надрукуйте перші n додатних цілих чисел із рівно двома заданими бітами в їх двійковому представленні.
Приклади:
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
А Просте рішення полягає в розгляді всіх натуральних чисел одне за одним, починаючи з 1. Для кожного числа перевірте, чи воно має рівно два набори бітів. Якщо число має рівно два встановлені біти, надрукуйте його та збільште кількість таких чисел.
C++
Ан Ефективне рішення це безпосередньо генерувати такі числа. Якщо ми чітко спостерігаємо за числами, ми можемо переписати їх, як наведено нижче pow(21)+pow(20) pow(22)+pow(20) pow(22)+pow(21) pow(23)+pow(20) pow(23)+pow(21) pow(23)+pow(22) .........
Усі числа можуть бути згенеровані в порядку зростання відповідно до старшого з двох встановлених бітів. Ідея полягає в тому, щоб виправити вищий з двох бітів один за іншим. Для поточного старшого встановленого біта врахуйте всі молодші біти та виведіть утворені числа.Java// C++ program to print first n numbers // with exactly two set bits #includeusing 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 ; } Python3// 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 KumarC## 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 SmithaJavaScript// 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< 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)Допоміжний простір: О(1)
Підхід №2: використання while і join
Підхід полягає в тому, щоб почати з цілого числа 3 і перевірити, чи дорівнює кількість встановлених бітів у його двійковому представленні 2 чи ні. Якщо він має рівно 2 встановлених біта, додайте його до списку чисел із 2 встановленими бітами, доки список не матиме n елементів.Алгоритм
1. Ініціалізуйте порожній список res для зберігання цілих чисел із рівно двома встановленими бітами.
C++
2. Ініціалізація цілочисельної змінної i до 3.
3. Якщо довжина списку res менше n, виконайте наступне:
a. Перевірте, чи кількість встановлених бітів у двійковому представленні i дорівнює 2 чи ні, використовуючи метод count() рядка.
b. Якщо кількість встановлених бітів дорівнює 2, то додайте i до списку res.
в. Збільште i на 1.
4. Повернути список рез.Java#include#include using namespace std ; int countSetBits ( int num ) { int count = 0 ; while ( num > 0 ) { count += num & 1 ; num >>= 1 ; } return count ; } vector < int > numbersWithTwoSetBits ( int n ) { vector < int > res ; int i = 3 ; while ( res . size () < n ) { if ( countSetBits ( i ) == 2 ) { res . push_back ( i ); } i ++ ; } return res ; } int main () { int n = 3 ; vector < int > result = numbersWithTwoSetBits ( n ); cout < < 'Result: ' ; for ( int i = 0 ; i < result . size (); i ++ ) { cout < < result [ i ] < < ' ' ; } cout < < endl ; return 0 ; } Python3// Java program for the above approach import java.util.ArrayList ; import java.util.List ; public class GFG { // Function to count the number of set bits (binary 1s) // in an integer static int countSetBits ( int num ) { int count = 0 ; while ( num > 0 ) { count += num & 1 ; // Increment count if the last // bit is set (1) num >>= 1 ; // Right shift to check the next bit } return count ; } // Function to generate 'n' numbers with exactly two set // bits in their binary representation static List < Integer > numbersWithTwoSetBits ( int n ) { List < Integer > res = new ArrayList <> (); int i = 3 ; // Start from 3 as the first number with // two set bits while ( res . size () < n ) { if ( countSetBits ( i ) == 2 ) { // Check if the number has exactly // two set bits res . add ( i ); // Add the number to the result list } i ++ ; // Move to the next number } return res ; } public static void main ( String [] args ) { int n = 3 ; // Number of numbers with two set bits to // generate List < Integer > result = numbersWithTwoSetBits ( n ); // Get the generated numbers for ( int num : result ) { System . out . print ( num + ' ' ); // Display the generated numbers } System . out . println (); } } // This code is contributed by Susobhan AkhuliC#def numbersWithTwoSetBits ( n ): res = [] i = 3 while len ( res ) < n : if bin ( i ) . count ( '1' ) == 2 : res . append ( i ) i += 1 return res n = 3 result = numbersWithTwoSetBits ( n ) output_string = ' ' . join ( str ( x ) for x in result ) print ( output_string )JavaScriptusing System ; using System.Collections.Generic ; class Program { // Function to count the number of set bits (binary 1s) in an integer static int CountSetBits ( int num ) { int count = 0 ; while ( num > 0 ) { count += num & 1 ; // Increment count if the last bit is set (1) num >>= 1 ; // Right shift to check the next bit } return count ; } // Function to generate 'n' numbers with exactly two set bits in their binary representation static List < int > NumbersWithTwoSetBits ( int n ) { List < int > res = new List < int > (); int i = 3 ; // Start from 3 as the first number with two set bits while ( res . Count < n ) { if ( CountSetBits ( i ) == 2 ) // Check if the number has exactly two set bits { res . Add ( i ); // Add the number to the result list } i ++ ; // Move to the next number } return res ; } static void Main ( string [] args ) { int n = 3 ; // Number of numbers with two set bits to generate List < int > result = NumbersWithTwoSetBits ( n ); // Get the generated numbers Console . Write ( 'Result: ' ); foreach ( int num in result ) { Console . Write ( num + ' ' ); // Display the generated numbers } Console . WriteLine (); } }
Вихід3 5 6Часова складність: O(n log n), де n — кількість цілих чисел із рівно двома встановленими бітами. Це тому, що ми перевіряємо кількість встановлених бітів у двійковому представленні кожного цілого числа, що займає O(log n) часу.
Просторова складність: O(n), де n – кількість цілих чисел із рівно двома встановленими бітами. Це тому, що ми зберігаємо список цілих чисел із двома встановленими бітами в пам’яті.
