การหาตัวเลขที่มี Set Bits เฉพาะระหว่างดัชนี L-th ถึง R-th โดยใช้ C++

ในปัญหาที่กำหนด เราต้องหาค่าของตัวเลขที่มี set bits ทั้งหมดอยู่ในช่วงที่กำหนด L, R ตัวอย่างเช่น:

Input: L = 1, R = 5
Output: 62
คำอธิบาย: การแทนค่าของ L และ R ที่กำหนดในรูปแบบไบนารีคือ 0..0111110

Input: L = 1, R = 4
Output: 30
คำอธิบาย: การแทนค่าของ L และ R ที่กำหนดในรูปแบบไบนารีคือ 0..11110

วิธีการแก้ปัญหา

ในปัญหาที่กำหนด เราจะอภิปรายสองวิธี คือ Brute Force และ Efficient Approach

วิธี Brute Force

ในวิธีนี้ เราจะเพียงแค่เดินทางผ่านช่วงที่กำหนดและบวกกำลังของ 2 ทั้งหมดในช่วงที่กำหนด และนั่นจะเป็นคำตอบของเรา

ตัวอย่าง

#include<bits/stdc++.h>
using namespace std;

int main() {
    int L = 1, R = 3; // ช่วงที่กำหนด
    int ans = 0; // คำตอบของเรา
    for(int i = L; i <= R; i++) // เดินทางผ่านทั้งช่วง
        ans += pow(2, i); // บวกค่าเข้าไปในคำตอบ
    cout << ans << "\n";
}

ผลลัพธ์

14

ในวิธีนี้ เราเพียงแค่เดินทางผ่านช่วงและบวกกำลังสองของตัวเลขในช่วง โปรแกรมนี้มีความซับซ้อนด้านเวลา O(N) โดยที่ N คือขนาดของช่วงของเรา แต่เราสามารถปรับปรุงความซับซ้อนด้านเวลาได้อีก โดยการนำความรู้ของ bit ในคำถามที่กำหนดมาใช้

วิธีที่มีประสิทธิภาพ (Efficient Approach)

ในวิธีนี้ เราจะสร้างสูตรที่จะคำนวณคำตอบให้เรา

ตัวอย่าง

#include<bits/stdc++.h>
using namespace std;

int main() {
    int L = 1, R = 3; // ช่วงที่กำหนด
    int ans = 0; // คำตอบของเรา
    // สูตร: (2^(R+1) - 1) - (2^L - 1) = 2^(R+1) - 2^L
    ans = (1 << (R + 1)) - (1 << L);
    cout << ans << "\n";
}

ผลลัพธ์

14

ในวิธีนี้ เราสร้างสูตรสำหรับคำนวณคำตอบของเรา

คำอธิบายโค้ด

เนื่องจากคุณรู้ว่าเราต้องคำนวณตัวเลขที่มี set bits ในช่วงที่กำหนด ดังนั้นในวิธีนี้ เราหาตัวเลขที่มี bit ตั้งค่าทั้งหมดจนถึง R จาก 0 แล้วเราต้องลบตัวเลขที่มี bit ตั้งค่าทั้งหมดจาก 1 ถึง (L-1) และดังนั้นเราจึงสร้างการสังเกตนี้ขึ้น ความซับซ้อนด้านเวลาทั้งหมดของโค้ดที่กำหนดคือ O(1) ซึ่งเป็นความซับซ้อนด้านเวลาคงที่ หมายความว่าเราสามารถคำนวณคำตอบใดๆ ในเวลาคงที่ได้

สรุป

บทความนี้จะทำโปรแกรมสำหรับ "Number with set bits only between L-th and R-th index" เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้และวิธีการแก้ปัญหาแบบเต็มรูปแบบ (ธรรมดาและมีประสิทธิภาพ) ที่เราใช้แก้ปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python และภาษาอื่นๆ ได้ เราหวังว่าบทความนี้จะเป็นประโยชน์