मान लें कि हमारे पास एक गोलाकार सरणी है जिसमें 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]
आधार शर्त हल है(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