n बच्चे एक वृत्त में खड़े हैं (सूचकांक 0 से n-1)। वितरण k-वें बच्चे से शुरू होता है (पहला सूचकांक 0)। हर k-वें बच्चे को गुब्बारा मिलता है और वह वृत्त छोड़ देता है। अंतिम गुब्बारा पाने वाले बच्चे का प्रारंभिक सूचकांक ढूंढें।
उदाहरण
इनपुट: n = 3, k = 2
आउटपुट: 1
चरण: बच्चे [0,1,2]। सूचकांक 2 (k=2) हटता है → [0,1]। अगला सूचकांक 0 हटता है → [1]। अंतिम = 1।
एल्गोरिदम (सिमुलेशन)
arr = list(range(n))बनाएं।init = 0(वर्तमान प्रारंभ सूचकांक)।- जब तक
len(arr) > 1:remove = (init + k) % len(arr)del arr[remove]init = remove(अगली गिनती यहीं से शुरू होती है)।
arr[0]वापस करें।
पायथन कार्यान्वयन
class Solution:
def solve(self, n, k):
arr = list(range(n))
init = 0
while len(arr) > 1:
remove = (init + k) % len(arr)
del arr[remove]
init = remove
return arr[0]
# परीक्षण
ob = Solution()
print(ob.solve(3, 2)) # 1
print(ob.solve(5, 3)) # 3
print(ob.solve(7, 3)) # 3
जोसेफस समस्या संबंध
यह क्लासिक जोसेफस समस्या का रूपांतर है। मानक जोसेफस में कदम k-1 होता है (0-आधारित)। यहां k कदम है। पुनरावृत्ति संबंध:
J(1, k) = 0
J(n, k) = (J(n-1, k) + k) % n
लेकिन यहां k के बजाय k+1 प्रभावी कदम है क्योंकि गिनती वर्तमान से शुरू होती है।
O(n) गणितीय समाधान
def josephus(n, k):
res = 0
for i in range(2, n + 1):
res = (res + k) % i
return res
इस समस्या के लिए k को k+1 से बदलें।
समय जटिलता
- सिमुलेशन: O(n²) (सूची हटाने के कारण)।
- गणितीय: O(n) समय, O(1) स्थान।