Дадено е число 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. За всяко число проверете дали има точно два набора бита. Ако дадено число има точно два зададени бита, отпечатайте го и увеличете броя на тези числа.
Ан Ефикасно решение е директно генериране на такива числа. Ако ясно наблюдаваме числата, можем да ги пренапишем, както е дадено по-долу pow(21)+pow(20) pow(22)+pow(20) pow(22)+pow(21) pow(23)+pow(20) pow(23)+pow(21) pow(23)+pow(22) .........
Всички числа могат да бъдат генерирани в нарастващ ред според по-високия от два зададени бита. Идеята е да се коригира по-висок от два бита един по един. За текущия по-висок зададен бит вземете предвид всички по-ниски битове и отпечатайте образуваните числа.
C++
// C++ program to print first n numbers // with exactly two set bits #include 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.
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>
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 ?> Изход:
bfs срещу dfs
3 5 6 9
Времева сложност: O(n)
java math.min
Помощно пространство: О(1)
Подход №2: Използване на while и join
Подходът е да се започне от цяло число 3 и да се провери дали броят на зададените битове в неговото двоично представяне е равен на 2 или не. Ако има точно 2 зададени бита, тогава го добавете към списъка с числа с 2 зададени бита, докато списъкът има n елемента.
Алгоритъм
1. Инициализирайте празен списък res за съхраняване на целите числа с точно два зададени бита.
2. Инициализирайте целочислена променлива i до 3.
3. Докато дължината на списъка res е по-малка от n, направете следното:
а. Проверете дали броят на зададените битове в двоичното представяне на i е равен на 2 или не, като използвате метода count() на низа.
b. Ако броят на зададените битове е равен на 2, тогава добавете i към списъка res.
c. Увеличете i с 1.
4. Върнете списъка res.
история на версиите на androidC++
#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; }
Java // 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 Akhuli
Python3 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)
C# using 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(); } }
JavaScript // Javascript program for the above approach // Function to count the number of set bits (binary 1s) // in an integer function countSetBits(num) { let 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 function numbersWithTwoSetBits(n) { let res = []; let i = 3; // Start from 3 as the first number with // two set bits while (res.length < n) { if (countSetBits(i) === 2) { // Check if the number has exactly // two set bits res.push(i); // Add the number to the result list } i++; // Move to the next number } return res; } // Number of numbers with two set bits to generate let n = 3; // Get the generated numbers let result = numbersWithTwoSetBits(n); // Display the generated numbers console.log(result.join(' ')); // This code is contributed by Susobhan Akhuli
Изход
3 5 6
Времева сложност: O(n log n), където n е броят цели числа с точно два зададени бита. Това е така, защото проверяваме броя на зададените битове в двоичното представяне на всяко цяло число, което отнема O(log n) време.
Пространствена сложност: O(n), където n е броят цели числа с точно два зададени бита. Това е така, защото ние съхраняваме списъка с цели числа с два зададени бита в паметта.