จำนวนขั้นตอนในการลดตัวเลขในรูปแบบไบนารีให้เหลือ 1 ด้วย C++

การลดตัวเลขไบนารีให้เหลือ 1

สมมติว่าเรามีตัวเลข s ในรูปแบบไบนารี เราต้องหาจำนวนขั้นตอนในการลดมันให้เหลือ 1 โดยปฏิบัติตามกฎดังนี้:

• ถ้าตัวเลขปัจจุบันเป็นเลขคู่ ให้หารด้วย 2
• ถ้าตัวเลขปัจจุบันเป็นเลขคี่ ให้บวก 1 เข้าไป

ตัวอย่าง

อินพุต: "1101" (คือ 13 ในฐานสิบ)

1. 13 เป็นเลขคี่ → บวก 1 ได้ 14
2. 14 เป็นเลขคู่ → หาร 2 ได้ 7
3. 7 เป็นเลขคี่ → บวก 1 ได้ 8
4. 8 เป็นเลขคู่ → หาร 2 ได้ 4
5. 4 เป็นเลขคู่ → หาร 2 ได้ 2
6. 2 เป็นเลขคู่ → หาร 2 ได้ 1

รวมทั้งหมด 6 ขั้นตอน

แนวทางแก้ปัญหา

เนื่องจากตัวเลขอาจใหญ่มาก จึงไม่สามารถแปลงเป็นจำนวนเต็มทั่วไปได้ ต้องจัดการกับสตริงไบนารีโดยตรง โดยใช้การบวกสตริงแบบไบนารี (Binary String Addition)

ขั้นตอนหลัก

1. ฟังก์ชัน addStrings() – บวกสองอาเรย์ของบิต (0/1) แบบ manual พร้อมจัดการ carry
2. ฟังก์ชัน addBinary() – เรียกใช้ addStrings()
3. ฟังก์ชัน makeVector() – แปลงสตริงไบนารีเป็นเวกเตอร์ของ int
4. ลูปหลัก – ทำซ้ำจนขนาดเวกเตอร์ = 1
   • ถ้าบิตท้ายเป็น 0 (เลขคู่) → ลบบิตท้ายออก (เทียบเท่าหาร 2)
   • ถ้าบิตท้ายเป็น 1 (เลขคี่) → บวก 1 ด้วย addBinary()
   • นับจำนวนรอบ

ตัวอย่างโค้ด C++

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

class Solution {
public:
    string addStrings(vector<int> num1, vector<int> num2) {
        vector<int> ret;
        int carry = 0, sum = 0;
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int i = 0, j = 0;
        while (i < num1.size() || j < num2.size()) {
            if (i < num1.size() && j < num2.size()) {
                sum = carry + num1[i] + num2[j];
                ret.push_back(sum % 2);
                carry = sum / 2;
                i++; j++;
            } else if (i < num1.size()) {
                sum = carry + num1[i];
                ret.push_back(sum % 2);
                carry = sum / 2;
                i++;
            } else {
                sum = carry + num2[j];
                ret.push_back(sum % 2);
                carry = sum / 2;
                j++;
            }
        }
        if (carry) ret.push_back(carry);
        string ans = "";
        for (int k = ret.size() - 1; k >= 0; k--)
            ans += (ret[k] + '0');
        return ans.empty() ? "0" : ans;
    }

    string addBinary(vector<int>& a, vector<int>& b) {
        return addStrings(a, b);
    }

    vector<int> makeVector(string v) {
        vector<int> ret;
        for (char c : v) ret.push_back(c - '0');
        return ret;
    }

    int numSteps(string s) {
        int ret = 0;
        vector<int> x = makeVector(s);
        while (x.size() > 1) {
            ret++;
            if (x.back() == 0) {
                x.pop_back(); // หาร 2
            } else {
                vector<int> temp(1, 1); // บวก 1
                x = makeVector(addBinary(x, temp));
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.numSteps("1101"); // Output: 6
    return 0;
}

การวิเคราะห์ความซับซ้อน

• เวลา: O(n²) ในกรณีแย่ที่สุด (n = ความยาวสตริง) เนื่องจากการบวก 1 อาจทำให้เกิด carry propagation ทุกครั้ง
• พื้นที่: O(n) สำหรับเก็บเวกเตอร์บิต

ข้อสังเกตเพิ่มเติม

สามารถเพิ่มประสิทธิภาพได้โดยสังเกตว่า: การบวก 1 กับเลขคี่จะทำให้บิต 1 ต่อเนื่องท้ายสุดกลายเป็น 0 และบิต 0 ตัวแรกจากขวาเป็น 1 (เช่น 1011 + 1 = 1100) ซึ่งช่วยลดจำนวนการดำเนินการได้