मान लीजिए हमारे पास एक साइज वेरिएबल N है, हमारे पास एक वेरिएबल SUM भी है जो सरणी में उपलब्ध सभी तत्वों का कुल योग है और एक और वेरिएबल K है जैसे कि सरणी में कोई भी तत्व K से बड़ा नहीं है। हमें एक ऑर्थोगोनल सरणी ढूंढनी है जहां सरणी के सभी तत्व विशिष्ट हों। यदि कोई समाधान नहीं है तो -1 लौटाएं।
यदि इनपुट N = 4, SUM = 16, K = 9 जैसा है, तो आउटपुट [1,2,4,9] होगा।
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- minimum_sum := (N * (N + 1)) / 2
- maximum_sum := (N * K) - (N * (N - 1)) / 2
- यदि minimum_sum > SUM या maximum_sum < SUM, तो -1 लौटाएं
- res := आकार N+1 की एक सरणी, 0 से N तक भरी हुई
- sum := minimum_sum
- i := N
- जब तक i >= 1, करें:
- x := sum + (K - i)
- यदि x < SUM, तो
- sum := sum + (K - i)
- res[i] := K
- K := K - 1
- अन्यथा,
- res[i] := res[i] + (SUM - sum)
- sum := SUM
- लूप से बाहर निकलें
- i := i - 1
- res लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
def get_arr(N, SUM, K):
minimum_sum = (N * (N + 1)) / 2
maximum_sum = (N * K) - (N * (N - 1)) / 2
if minimum_sum > SUM or maximum_sum < SUM:
return -1
res = [i for i in range(N + 1)]
sum = minimum_sum
i = N
while i >= 1:
x = sum + (K - i)
if x < SUM:
sum = sum + (K - i)
res[i] = K
K -= 1
else:
res[i] += (SUM - sum)
sum = SUM
break
i -= 1
return res
N = 4
SUM = 16
K = 9
print(get_arr(N, SUM, K))
इनपुट
4, 16, 9
आउटपुट
[0, 1, 2, 4.0, 9]
