নেক্সট স্পার্স নম্বর খুঁজে বের করা C++-এ

এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যা N দেওয়া আছে। আমাদের কাজ হল নেক্সট স্পার্স নম্বর বের করার প্রোগ্রাম লিখা।

স্পার্স নম্বর হল একটি বিশেষ ধরনের সংখ্যা যার বাইনারি রিপ্রেজেন্টেশনে কোনো দুটি সংলগ্ন ১ থাকে না।

উদাহরণ: 5 (101), 16 (10000)

সমস্যা বর্ণনা - দেওয়া সংখ্যা N-এর চেয়ে বড় সবচেয়ে ছোট স্পার্স নম্বর বের করতে হবে।

উদাহরণ

ইনপুট

N = 7

আউটপুট

8

ব্যাখ্যা

৮-এর বাইনারি 1000 যা N-এর চেয়ে বড় সবচেয়ে ছোট স্পার্স নম্বর।

সমাধানের পদ্ধতি

এই সমস্যার সহজ সমাধান হল N-এর চেয়ে বড় সব সংখ্যা চেক করা। এবং প্রথম স্পার্স নম্বর পাওয়া পর্যন্ত চলতে থাকা।

এ জন্য N থেকে অনন্ত পর্যন্ত লুপ চালাতে হবে এবং প্রতিটি সংখ্যা চেক করতে হবে যে সেটি স্পার্স নম্বর কিনা। যদি হ্যাঁ, তবে লুপ ব্রেক করুন অন্যথায় চালিয়ে যান।

প্রোগ্রাম উদাহরণ (সহজ পদ্ধতি)

#include <iostream>
using namespace std;

bool isSparseNumber(int N) {
    int currentBit = (N & 1);
    int nextBit;
    
    while (N != 0) {
        nextBit = currentBit;
        currentBit = (N & 1);
        N >>= 1;
        if (nextBit == currentBit && nextBit == 1 && currentBit == 1)
            return false;
    }
    return true;
}

int findNextSparseNumber(int N) {
    while (1) {
        if (isSparseNumber(N))
            return N;
        N++;
    }
    return -1;
}

int main() {
    int N = 564;
    cout << "The number is " << N << endl;
    cout << "The next Sparse Number is " << findNextSparseNumber(N);
    return 0;
}

আউটপুট

The number is 564
The next Sparse Number is 576

দক্ষ পদ্ধতি (বিট ম্যানিপুলেশন)

এই সমস্যার একটি দক্ষ পদ্ধতি হল সংখ্যার বিট ম্যানিপুলেট করা। এর জন্য সংখ্যার বাইনারি বের করে সেখানে সংলগ্ন ১ থাকা বিটগুলো ম্যানিপুলেট করব। LSB থেকে MSB দিকে ট্রাভার্স করব, যখন দুটি সংলগ্ন ১ পাব, তখন দুটো ১ কে ০ করে দিব এবং পরবর্তী বিটকে ১ করব। এবং MSB পর্যন্ত এটি করব। তারপর বাইনারি নম্বরটিকে ডেসিমলে কনভার্ট করব যা আমাদের ফলাফল।

উদাহরণ:

N = 52

বাইনারি: 110100

LSB থেকে ট্রাভার্স করলে প্রথম সংলগ্ন ১ পাওয়া যায়: 110100 (হাইলাইটেড অংশ)। তারপর দুটি ১ কে ০ করে পরবর্তী বিটে ১ যোগ করলে হয় 1000000, যেটির ডেসিমেল হল 64।

প্রোগ্রাম উদাহরণ (দক্ষ পদ্ধতি)

#include <iostream>
using namespace std;

int findNextSparseNumber(int N) {
    int spNum[16];
    int n = 0;
    
    // বাইনারি বיטים স্টোর
    while (N != 0) {
        spNum[n] = (N & 1);
        n++;
        N >>= 1;
    }
    n++;
    
    int lastCorrectedBit = 0;
    for (int i = 0; i < n; i++) {
        if (spNum[i] == 1 && spNum[i-1] == 1 && spNum[i+1] != 1) {
            spNum[i+1] = 1;
            for (int j = i; j >= lastCorrectedBit; j--)
                spNum[j] = 0;
            lastCorrectedBit = i + 1;
        }
    }
    
    int sparseNumber = 0;
    for (int i = 0; i < n-1; i++)
        sparseNumber += spNum[i] * (1 << i);
    
    return sparseNumber;
}

int main() {
    int N = 564;
    cout << "The number is " << N << endl;
    cout << "The next Sparse Number is " << findNextSparseNumber(N);
    return 0;
}

আউটপুট

The number is 564
The next Sparse Number is 576