Dat un număr n, se afișează primele n numere întregi pozitive cu exact doi biți stabiliți în reprezentarea lor binară.
Exemple:
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
O Soluție simplă este de a lua în considerare toate numerele întregi pozitive unul câte unul începând de la 1. Pentru fiecare număr verificați dacă are exact două seturi de biți. Dacă un număr are exact doi biți setați, imprimați-l și creșteți numărul acestor numere.
Un Soluție eficientă este de a genera direct astfel de numere. Dacă observăm în mod clar numerele, le putem rescrie așa cum este prezentat mai jos pow(21)+pow(20) pow(22)+pow(20) pow(22)+pow(21) pow(23)+pow(20) pow(23)+pow(21) pow(23)+pow(22) .........
Toate numerele pot fi generate în ordine crescătoare în funcție de mai mare dintre doi biți setați. Ideea este să remediați mai mult de doi biți unul câte unul. Pentru bitul setat mai mare, luați în considerare toți biții mai mici și imprimați numerele formate.
C++
// C++ program to print first n numbers // with exactly two set bits #include
// 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 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# 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.
<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 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 ?> Ieșire:
java este instanceof
3 5 6 9
Complexitatea timpului: Pe)
java matematică.min
Spațiu auxiliar: O(1)
Abordarea #2: Folosind while și join
Abordarea este de a începe de la întregul 3 și de a verifica dacă numărul de biți setați în reprezentarea sa binară este egal cu 2 sau nu. Dacă are exact 2 biți setați, adăugați-l la lista de numere cu 2 biți setați până când lista are n elemente.
Algoritm
1. Inițializați o listă goală pentru a stoca numerele întregi cu exact doi biți setați.
2. Inițializați o variabilă întreagă i la 3.
3. În timp ce lungimea listei res este mai mică decât n, faceți următoarele:
o. Verificați dacă numărul de biți setați în reprezentarea binară a lui i este egal cu 2 sau nu folosind metoda count() a șirului.
b. Dacă numărul de biți setați este egal cu 2, adăugați i la lista res.
c. Creșteți i cu 1.
4. Întoarceți lista res.
#include
// 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
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)
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 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
Ieșire
3 5 6
Complexitatea timpului: O(n log n) unde n este numărul de numere întregi cu exact doi biți setați. Acest lucru se datorează faptului că verificăm numărul de biți setați în reprezentarea binară a fiecărui număr întreg care ia timp O(log n).
Complexitatea spațiului: O(n) unde n este numărul de numere întregi cu exact doi biți stabiliți. Acest lucru se datorează faptului că stocăm în memorie lista de numere întregi cu doi biți setați.
zăpadă vs gheață