১ থেকে n পর্যন্ত পূর্ণসংখ্যা ধারণকারী একটি সার্কুলার (circular) অ্যারে দেওয়া থাকলে, প্রথম উপাদান থেকে শুরু করে প্রতিটি দ্বিতীয় উপাদান ডিলিট করলে শেষে কোন উপাদান বাঁচবে, তা বের করতে হবে। ইনপুট ৫ হলে অ্যারে [1, 2, 3, 4, 5]। ১ থেকে শুরু করে প্রতিটি দ্বিতীয় উপাদান ডিলিট করলে:
1 0 3 4 5 1 0 3 0 5 0 0 3 0 5 0 0 3 0 0
তাই বাঁচা উপাদান ৩।
এটি রিকারশন (recursion) দিয়ে সমাধান করা যাবে। n জোড় হলে ২, ৪, ৬... সরানো হয়, আবার ১ থেকে শুরু হয়। তাই n/2 সংখ্যা সরানো হয়। এবং আমরা ১, ৩, ৫... n/2 শুধু বিজোড় সংখ্যাগুলো নিয়ে n/2 আকারের অ্যারেতে যেন নতুন করে শুরু করছি। সূত্র:
solve(n)=2*solve(n/2)-1 [যখন n জোড়] solve(n)=2*solve((n-1)/2)+1 [যখন n বিজোড়]
বেস কন্ডিশন: 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
