मान लीजिए हमारे पास k संख्या में कैंडी हैं। हमें उन्हें बच्चों के बीच वितरित करना है। अब कुछ नियम हैं:
- i-वां बच्चे को i^2 संख्या में कैंडी मिलेगी
- इंडेक्स i पर कोई भी बच्चा तब तक कैंडी नहीं पाएगा जब तक इंडेक्स 1 से i-1 तक के सभी बच्चों को सर्व नहीं किया जाता
- यदि i-वां बच्चा i^2 संख्या में कैंडी नहीं पाता है, तो वह वैध वितरण नहीं है।
तो, यदि इनपुट k = 20 है, तो आउटपुट 3 होगा क्योंकि, पहला 1 पाएगा, दूसरा 2^2 = 4 पाएगा, तीसरा 3^2 = 9 पाएगा, लेकिन चौथे को 4^2 = 16 चाहिए, लेकिन हमारे पास केवल 6 कैंडी बची हैं, इसलिए यह वैध वितरण नहीं है, इसलिए केवल तीन बच्चों को सर्व किया जाएगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- left := 0, right := k
- जब right - left > 1, करें
- mid := floor of (left + right) / 2
- यदि floor of (mid * (mid + 1) * (2 * mid + 1) / 6) > k, तो
- right := mid
- अन्यथा,
- left := mid
- यदि right *(right + 1) *(2 * right + 1) <= k * 6, तो
- right वापस करें
- left वापस करें
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
def solve(k): left = 0 right = k while (right - left > 1): mid = (left + right) // 2 if (mid * (mid + 1) * (2 * mid + 1) // 6 > k): right = mid else: left = mid if (right * (right + 1) * (2 * right + 1) <= k * 6): return right return left k = 20 print(solve(k))
इनपुट
20
आउटपुट
3
