logo

Tulosta ensimmäiset n numeroa täsmälleen kahdella bitillä

Annettu luku n tulostaa ensimmäiset n positiivista kokonaislukua, joissa on täsmälleen kaksi bittiä niiden binääriesityksessä.
Esimerkkejä:

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 Yksinkertainen Ratkaisu on tarkastella kaikkia positiivisia kokonaislukuja yksitellen alkaen 1. Tarkista jokaisen luvun kohdalla, onko siinä täsmälleen kaksi joukkoa bittiä. Jos numerossa on täsmälleen kaksi asetettua bittiä, tulosta se ja lisää tällaisten lukujen määrää.
An Tehokas Ratkaisu on luoda suoraan tällaisia ​​numeroita. Jos tarkkailemme numeroita selkeästi, voimme kirjoittaa ne uudelleen alla esitetyllä tavalla pow(21)+pow(20) pow(22)+pow(20) pow(22)+pow(21) pow(23)+pow(20) pow(23)+pow(21) pow(23)+pow(22) .........
Kaikki luvut voidaan generoida kasvavassa järjestyksessä kahdesta suuremman bitin mukaan. Ajatuksena on korjata kahdesta bitistä korkeampi yksitellen. Nykyisen korkeamman bitin kohdalla huomioi kaikki alemmat bitit ja tulosta muodostetut numerot.



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 ?> 

Lähtö:  
 

mitkä kuukaudet ovat Q3
3 5 6 9  


Aika monimutkaisuus: O(n)

java int merkkijonona

Aputila: O(1)



Lähestymistapa 2: While- ja join-käyttö


Lähestymistapa on aloittaa kokonaisluvusta 3 ja tarkistaa, onko asetettujen bittien määrä sen binääriesituksessa yhtä suuri kuin 2 vai ei. Jos siinä on täsmälleen 2 sarjabittiä, lisää se numeroluetteloon 2 bittijoukolla, kunnes luettelossa on n elementtiä.

Algoritmi

1. Alusta tyhjä lista res tallentaaksesi kokonaisluvut täsmälleen kahdella bitillä.
2. Alusta kokonaislukumuuttuja i arvoon 3.
3. Kun luettelon pituus on pienempi kuin n, toimi seuraavasti:
a. Tarkista, onko i:n binääriesityksen joukkobittien määrä yhtä suuri kuin 2 vai ei, käyttämällä merkkijonon count()-menetelmää.
b. Jos asetettujen bittien määrä on 2, lisää i luetteloon res.
c. Kasvata i:llä 1.
4. Palauta luettelo res.

merkkijono chatille
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 

Lähtö
3 5 6

Ajan monimutkaisuus: O(n log n), jossa n on kokonaislukujen määrä, joissa on täsmälleen kaksi asetettua bittiä. Tämä johtuu siitä, että tarkistamme asetettujen bittien lukumäärän kunkin kokonaisluvun binääriesityksessä, joka vie O(log n) aikaa.



Avaruuden monimutkaisuus: O(n) missä n on kokonaislukujen määrä, joissa on täsmälleen kaksi asetettua bittiä. Tämä johtuu siitä, että tallennamme muistiin kokonaislukuluettelon kahdella bitillä.