বিবেচনা করুন আমাদের একটি বৃত্তাকার অ্যারে রয়েছে যেখানে 1 থেকে n পর্যন্ত পূর্ণসংখ্যা রয়েছে। শেষ উপাদানটি খুঁজুন, যা প্রথম উপাদান থেকে শুরু করে প্রতিটি দ্বিতীয় উপাদান মুছে ফেলার পরে তালিকায় থাকবে। যদি ইনপুট 5 হয়, তাহলে অ্যারে হবে [1, 2, 3, 4, 5]। 1 থেকে শুরু করুন। মুছে ফেলার পর প্রতিটি সেকেন্ড এলিমেন্ট −
এর মত হবে1 0 3 4 5 1 0 3 0 5 0 0 3 0 5 0 0 3 0 0
সুতরাং তালিকায় থাকা উপাদানটি হল 3।
আমরা পুনরাবৃত্তি ব্যবহার করে এই সমস্যার সমাধান করব। ধরুন n জোড়। সংখ্যা 2, 4, 6 মুছে ফেলা হবে, তারপর আমরা আবার 1 থেকে শুরু করব। তাই n/2 সংখ্যা মুছে ফেলা হয়। এবং আমরা শুরু করি যেন n/2 এর একটি অ্যারেতে ফর্ম 1 যেটিতে শুধুমাত্র বিজোড় সংখ্যা 1, 3, 5, … n/2 রয়েছে। তাই আমরা −
এর মত সূত্র লিখতে পারিsolve(n)=2*solve(n/2)-1[when n is even] solve(n)=2*solve(n-1/2)+1[when n is odd]
বেস কন্ডিশন হল solve(1) =1.
উদাহরণ
#include<iostream>
using namespace std;
int deleteSecondElement(int n) {
if (n == 1)
return 1;
if (n % 2 == 0)
return 2 * deleteSecondElement(n / 2) - 1;
else
return 2 * deleteSecondElement(((n - 1) / 2)) + 1;
}
int main() {
int n = 5;
cout << "Remaining Element: " << deleteSecondElement(n) << endl;
n = 10;
cout << "Remaining Element: " << deleteSecondElement(n) << endl;
} আউটপুট
Remaining Element: 3 Remaining Element: 5
