এই সমস্যাতে, আমাদের একটি নম্বরের বাইনারি রিপ্রেজেন্টেশন দেওয়া আছে এবং আমাদের নেক্সট নম্বর অর্থাৎ দেয়া নম্বর সাথে ১ যোগ করলে যা আসে তার বাইনারি রিপ্রেজেন্টেশন বের করতে হবে।
বাইনারি রিপ্রেজেন্টেশন হলো একটি নম্বরের বেস ২-এ কনভার্ট করে শুধু ০ বা ১ দিয়ে রিপ্রেজেন্ট করা।
উদাহরণস্বরূপ, ১৪-এর বাইনারি রিপ্রেজেন্টেশন 1110।
তবে, আমাদের একটি নম্বর n বাইনারি ফর্মে দেওয়া থাকবে। এবং আমাদের n+1-এর বাইনারি রিপ্রেজেন্টেশন বের করতে হবে।
এই সমস্যা সমাধান করতে হলে বাইনারি অ্যাডিশনের বেসিক জানতে হবে। ০ বা ১ সাথে ১ যোগ করলে বাইনারি-তে কী হয় তা দেখি:
0 + 1 = 1
1 + 1 = 10
উদাহরণ
উদাহরণ দিয়ে দেখি কিভাবে সমাধান করব:
ইনপুট: 010010111 আউটপুট: 010011000 ব্যাখ্যা: (010010111)₂ হলো ১৫২-এর বাইনারি রিপ্রেজেন্টেশন এবং নেক্সট নম্বর হবে ১৫৩ যার বাইনারি রিপ্রেজেন্টেশন (010011000)₂। আমরা বাইনারি অ্যাডিশন ব্যবহার করব এবং বাইনারি (1)₂ নম্বরের বাইনারি রিপ্রেজেন্টেশনে যোগ করব।
উপরের উদাহরণ থেকে দেখা যাচ্ছে যে বাইনারি ১ যোগ করলে ডান দিক থেকে সব ১ গুলো ০ হয়ে যায়, যতক্ষণ না প্রথম ০ পাওয়া যায় এবং সেই ০ কে ১ করে ফ্লিপ করা হয়। এখন এই লজিকের জন্য অ্যালগরিদম বানাই।
অ্যালগরিদম
ধাপ ১: ডান থেকে বাম শুরু করুন অর্থাৎ n-1 থেকে 0 ধাপ ২: ০ পাওয়া গেলে সেটি ১ করুন এবং ব্রেক করুন ধাপ ৩: ১ পাওয়া গেলে সেটি ০ করুন ধাপ ৪: কোনো ০ না পাওয়া গেলে, অ্যারের শুরুতে ১ যোগ করুন ধাপ ৫: অ্যারে প্রিন্ট করুন
উদাহরণ
এখন, এই অ্যালগরিদমের কোড বাস্তবায়ন দেখি।
#include <bits/stdc++.h>
using namespace std;
string nextBinary(string num) {
int l = num.size();
int flag = 0;
for (int i = l - 1; i >= 0; i--) {
if (num.at(i) == '0') {
num.at(i) = '1';
flag = 1;
break;
} else
num.at(i) = '0';
}
if (flag < 0)
num = "1" + num;
return num;
}
int main() {
string number = "0111010111";
cout << "The Binary representation of the number is " << number << endl;
cout << "Binary representation of next number is " << nextBinary(number);
return 0;
}
আউটপুট
The Binary representation of the number is 0111010111 Binary representation of next number is 0111011000
