এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যার মান দেওয়া হয়েছে। আমাদের কাজ হল পরবর্তী স্পেয়ার সংখ্যা খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা।
স্পার্স নম্বর একটি বিশেষ ধরনের সংখ্যা যার বাইনারি রূপান্তরে কোনো সংলগ্ন 1 নেই।
Example: 5(101) , 16(10000)
সমস্যা বর্ণনা − প্রদত্ত সংখ্যা N-এর জন্য, আমাদের N-এর চেয়ে বড় ক্ষুদ্রতম সংখ্যাটি খুঁজে বের করতে হবে যা একটি স্পার্স সংখ্যা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
N = 7
আউটপুট
8
ব্যাখ্যা
8-এর বাইনারি হল 1000 যা এটিকে n-এর থেকে সবচেয়ে ছোট স্পার্স সংখ্যা করে তোলে।
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল N-এর চেয়ে বড় সমস্ত সংখ্যার জন্য পরীক্ষা করা এবং আমাদের প্রথম স্পার্স নম্বর না পাওয়া পর্যন্ত থামানো।
এর জন্য আমাদের N থেকে অসীম পর্যন্ত লুপ করতে হবে এবং প্রতিটি সংখ্যার জন্য এটি একটি স্পার্স নম্বর কিনা তা পরীক্ষা করতে হবে। যদি হ্যাঁ, লুপ ভাঙুন অন্যথায় চালিয়ে যান৷
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include<iostream>
using namespace std;
bool isSpareNumber(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(isSpareNumber(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
দক্ষ পদ্ধতি
সমস্যার একটি দক্ষ পদ্ধতি হল সংখ্যার বিটগুলিকে ম্যানিপুলেট করা। এর জন্য আমরা সংখ্যার বাইনারি খুঁজে বের করব এবং যেখানে সংলগ্নতা ঘটেছে সেই বিটগুলিকে ম্যানিপুলেট করব। সর্বনিম্ন তাৎপর্যপূর্ণ বিট থেকে সর্বাধিক গুরুত্বপূর্ণ বিট পর্যন্ত যাত্রা করে, যখন আমরা 1 এর জোড়ার মুখোমুখি হই, তখন আমরা উভয় 1 এর 0 এর সাথে প্রতিস্থাপন করব এবং পরবর্তী বিট 1 করব। এবং যতক্ষণ না আমরা MSB-এ পৌঁছাই ততক্ষণ পর্যন্ত এটি করব। এবং তারপর সংখ্যাটি বাইনারি সংখ্যাটিকে দশমিক সংখ্যায় রূপান্তর করুন যা আমাদের ফলাফল।
এখানে একটি উদাহরণ নেওয়া যাক,
N =52
সংখ্যাটির বাইনারি হল 110100
আমরা LSB থেকে অতিক্রম করব এবং বাইনারিতে পরপর 1 এর প্রথম জোড়া খুঁজে পাব। এটি হল 11৷ 0100 হাইলাইট করা অংশ। তারপর, আমরা 0 এর সাথে উভয় 1 এর প্রতিস্থাপন করব এবং পরবর্তী বিটে একটি যোগ করব। এটি সংখ্যাটিকে 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
