정확히 2개의 설정된 비트를 사용하여 처음 n개 숫자를 인쇄합니다.
숫자 n이 주어지면 먼저 이진 표현에 정확히 2개의 비트가 설정된 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
시간 복잡도: 에)보조 공간: 오(1)
접근법#2: while 및 조인 사용
접근 방식은 정수 3부터 시작하여 이진 표현의 설정된 비트 수가 2인지 여부를 확인하는 것입니다. 정확히 2개의 세트 비트가 있는 경우 목록에 n개의 요소가 있을 때까지 2개의 세트 비트가 있는 숫자 목록에 이를 추가합니다.연산
1. 빈 목록 res를 초기화하여 정확히 2개의 비트 세트로 정수를 저장합니다.
C++
2. 정수 변수 i를 3으로 초기화합니다.
3. 목록 res의 길이가 n보다 작은 동안 다음을 수행합니다.
에이. i의 이진 표현에서 설정된 비트 수가 2인지 여부를 문자열의 count() 메서드를 사용하여 확인합니다.
비. 설정된 비트 수가 2이면 목록 res에 i를 추가합니다.
기음. i를 1씩 증가시킵니다.
4. 목록 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 (); } }
산출3 5 6시간 복잡도: O(n log n) 여기서 n은 정확히 2개의 비트가 설정된 정수의 수입니다. 이는 O(log n) 시간이 걸리는 각 정수의 이진 표현에서 설정된 비트 수를 확인하기 때문입니다.
공간 복잡도: O(n) 여기서 n은 정확히 2개의 비트가 설정된 정수의 수입니다. 이는 두 개의 세트 비트가 있는 정수 목록을 메모리에 저장하기 때문입니다.
