Išspausdinkite pirmuosius n skaičių su tiksliai dviem nustatytais bitais
Duotas skaičius n atspausdina pirmuosius n teigiamų sveikųjų skaičių, kurių dvejetainiame atvaizde yra tiksliai du nustatyti bitai.
Pavyzdžiai:
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 Paprastas Sprendimas yra svarstyti visus teigiamus sveikuosius skaičius po vieną, pradedant nuo 1. Kiekvienam skaičiui patikrinkite, ar jis turi tiksliai du bitų rinkinius. Jei skaičius turi tiksliai du nustatytus bitus, atspausdinkite jį ir padidinkite tokių skaičių skaičių.
C++
An Efektyvus Sprendimas yra tiesiogiai generuoti tokius skaičius. Jei aiškiai stebime skaičius, galime juos perrašyti taip, kaip nurodyta toliau pow(21)+pow(20) pow(22)+pow(20) pow(22)+pow(21) pow(23)+pow(20) pow(23)+pow(21) pow(23)+pow(22) .........
Visi skaičiai gali būti generuojami didėjančia tvarka pagal didesnį iš dviejų nustatytų bitų. Idėja yra taisyti aukščiau iš dviejų bitų po vieną. Dabartiniam didesniam bitui apsvarstykite visus žemesnius bitus ir atspausdinkite suformuotus skaičius.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>Išvestis:
3 5 6 9
Laiko sudėtingumas: O(n)Pagalbinė erdvė: O(1)
2 metodas: naudokite while ir join
Metodas yra pradėti nuo sveikojo skaičiaus 3 ir patikrinti, ar nustatytų bitų skaičius jo dvejetainiame atvaizde yra lygus 2, ar ne. Jei jis turi tiksliai 2 rinkinius, pridėkite jį prie skaičių sąrašo su 2 rinkiniais, kol sąraše bus n elementų.Algoritmas
1. Inicijuokite tuščią sąrašo res, kad išsaugotumėte sveikuosius skaičius su tiksliai dviem nustatytais bitais.
C++
2. Inicijuokite sveikojo skaičiaus kintamąjį nuo i iki 3.
3. Kol sąrašo res ilgis yra mažesnis nei n, atlikite šiuos veiksmus:
a. Naudodami eilutės metodą count() patikrinkite, ar rinktinių bitų skaičius dvejetainiame i atvaizde yra lygus 2, ar ne.
b. Jei nustatytų bitų skaičius yra lygus 2, tada pridėkite i prie sąrašo res.
c. Padidinkite i 1.
4. Grąžinkite sąrašo res.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 (); } }
Išvestis3 5 6Laiko sudėtingumas: O(n log n), kur n yra sveikųjų skaičių su tiksliai dviem nustatytais bitais skaičius. Taip yra todėl, kad tikriname nustatytų bitų skaičių dvejetainėje kiekvieno sveikojo skaičiaus atvaizde, kuriam reikia O (log n) laiko.
Erdvės sudėtingumas: O(n), kur n yra sveikųjų skaičių su tiksliai dviem nustatytais bitais skaičius. Taip yra todėl, kad atmintyje saugome sveikųjų skaičių su dviem nustatytais bitais sąrašą.
