Nyomtassa ki az első n számot pontosan két beállított bittel
Adott n szám először n pozitív egész számot ír ki pontosan két bittel a bináris ábrázolásukban.
Példák:
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 Egyszerű Megoldás Az összes pozitív egész számot egyenként kell figyelembe venni 1-től kezdve. Minden számnál ellenőrizze, hogy pontosan két bitkészlete van-e. Ha egy számnak pontosan két beállított bitje van, nyomtassa ki, és növelje az ilyen számok számát.
C++
An Hatékony megoldás az ilyen számok közvetlen generálása. Ha jól megfigyeljük a számokat, átírhatjuk őket az alábbiak szerint: pow(21)+pow(20) pow(22)+pow(20) pow(22)+pow(21) pow(23)+pow(20) pow(23)+pow(21) pow(23)+pow(22) .........
Minden szám generálható növekvő sorrendben a két bit közül a magasabb érték szerint. Az ötlet az, hogy két bit közül a magasabbat egyenként rögzítsék. Az aktuális magasabb beállított biteknél vegye figyelembe az összes alacsonyabb bitet, és nyomtassa ki a képzett számokat.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>Kimenet:
3 5 6 9
Időbeli összetettség: On)Kiegészítő tér: O(1)
2. megközelítés: A while és a join használata
A megközelítés az, hogy a 3-as egész számból indulunk ki, és ellenőrizzük, hogy a beállított bitek száma a bináris ábrázolásban egyenlő-e 2-vel vagy sem. Ha pontosan 2 beállított bitje van, akkor add hozzá a számok listájához 2 készletbittel, amíg a lista n elemű lesz.Algoritmus
1. Inicializáljon egy üres listát, hogy pontosan két bittel tárolja az egész számokat.
C++
2. Inicializáljon egy egész i változót 3-ra.
3. Amíg a lista res hossza kisebb, mint n, tegye a következőket:
a. A karakterlánc count() metódusával ellenőrizze, hogy az i bináris reprezentációjában lévő beállított bitek száma egyenlő-e 2-vel, vagy sem.
b. Ha a beállított bitek száma egyenlő 2-vel, akkor a res listához fűzze i-t.
c. Növelje az i-t 1-gyel.
4. Adja vissza a listát.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 (); } }
Kimenet3 5 6Időbonyolultság: O(n log n), ahol n a pontosan két beállított bittel rendelkező egész számok száma. Ennek az az oka, hogy ellenőrizzük a beállított bitek számát minden egyes egész szám bináris megjelenítésében, amely O(log n) időt vesz igénybe.
Térkomplexitás: O(n), ahol n a pontosan két beállított bittel rendelkező egész számok száma. Ennek az az oka, hogy a memóriában tároljuk a két bites egész számok listáját.
