मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है जिसकी लंबाई n है। इस सूची में मौजूद तत्व एक प्रतियोगिता में तैराकों के वर्तमान स्कोर का प्रतिनिधित्व कर रहे हैं। फाइनल मैच के लिए इस वर्तमान दौर का प्रथम स्थान विजेता n स्कोर प्राप्त करेगा, द्वितीय स्थान विजेता n-1 अंक प्राप्त करेगा और इसी तरह। हमें उन तैराकों की संख्या जांचनी है जो वर्तमान दौर के बाद फाइनल दौर में अभी भी प्रतियोगिता जीत सकते हैं। यदि अंकों में प्रथम स्थान के लिए टाई है, तो उसे भी जीत के रूप में गिना जाएगा।
इसलिए, यदि इनपुट है nums = [9, 6, 11, 12], तो आउटपुट होगा 3, क्योंकि वर्तमान में 9, 11 और 12 अंक वाले तैराक सभी जीत सकते हैं यदि फाइनल स्कोर [13, 9, 13, 13] है। अर्थात, 9 अंक वाले तैराक को प्रथम स्थान मिला तो 4 अतिरिक्त अंक मिले, फिर 6 अंक वाले तैराक को द्वितीय स्थान मिला तो अब स्कोर 9 है। 11 अंक वाले तैराक को तृतीय स्थान मिला तो नया स्कोर 13 है, और 12 अंक वाले तैराक को अंतिम स्थान मिला तो स्कोर 12 भी है। लेकिन भले ही 6 अंक वाला तैराक प्रथम स्थान प्राप्त करे तो उसका अंतिम स्कोर 10 अंक होगा, 9 अंक वाला तैराक द्वितीय स्थान प्राप्त करेगा तो उसका स्कोर 12 होगा और इसी तरह, तब भी दूसरे तैराक के लिए जीत का कोई मौका नहीं है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
- यदि
numsखाली है, तो:0लौटाएं
n := numsका आकारans := 0numsसूची को सॉर्ट करेंa := 0iके लिएn - 1से 0 तक, 1 से घटाते हुए, करें:cand := nums[i] + n - i- यदि
cand > a, तो:a := cand
numsमें प्रत्येकxके लिए, करें:- यदि
x + n >= a, तो:ans := ans + 1
- यदि
ansलौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
def solve(nums):
if not nums:
return 0
n = len(nums)
ans = 0
nums.sort()
a = 0
for i in range(n - 1, -1, -1):
cand = nums[i] + n - i
if cand > a:
a = cand
for x in nums:
if x + n >= a:
ans += 1
return ans
nums = [9, 6, 11, 12]
print(solve(nums))
इनपुट
[9, 6, 11, 12]
आउटपुट
3