logo

Отпечатайте първите 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. За всяко число проверете дали има точно два набора бита. Ако дадено число има точно два зададени бита, отпечатайте го и увеличете броя на тези числа.
Ан Ефикасно решение е директно генериране на такива числа. Ако ясно наблюдаваме числата, можем да ги пренапишем, както е дадено по-долу 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.

история на версиите на android
C++
#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 е броят цели числа с точно два зададени бита. Това е така, защото ние съхраняваме списъка с цели числа с два зададени бита в паметта.