بالنظر إلى رقم 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 ?> الإخراج :
التعبير العادي في جافا
3 5 6 9
تعقيد الوقت : على)
عداد جافا
المساحة المساعدة: يا(1)
النهج رقم 2: استخدام while والانضمام
يتمثل النهج في البدء من العدد الصحيح 3 والتحقق مما إذا كان عدد البتات المحددة في تمثيله الثنائي يساوي 2 أم لا. إذا كانت تحتوي على مجموعتين من البتات بالضبط، فقم بإضافتها إلى قائمة الأرقام التي تحتوي على مجموعتين من البتات حتى تحتوي القائمة على عناصر n.
خوارزمية
1. قم بتهيئة قائمة فارغة لتخزين الأعداد الصحيحة مع مجموعتين من البتات بالضبط.
2. قم بتهيئة متغير عدد صحيح من i إلى 3.
3. بينما يكون طول دقة القائمة أقل من n، قم بما يلي:
أ. تحقق مما إذا كان عدد البتات المحددة في التمثيل الثنائي لـ i يساوي 2 أم لا باستخدام طريقة count() للسلسلة.
ب. إذا كان عدد البتات المحددة يساوي 2، فقم بإلحاق i بقائمة الدقة.
ج. زيادة أنا بمقدار 1.
4. قم بإرجاع دقة القائمة.
#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 هو عدد الأعداد الصحيحة التي تحتوي على مجموعتين من البتات بالضبط. وذلك لأننا نقوم بتخزين قائمة الأعداد الصحيحة المكونة من مجموعتين من البتات في الذاكرة.