मान लें हमारे पास 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 संख्याएं हटा दी गई हैं। और हम ऐसे शुरू करते हैं जैसे 1 से n/2 की सरणी में जिसमें केवल विषम अंक 1, 3, 5, ... 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
