पायथन में दिए गए आकार, योग और ऊपरी सीमा के साथ विशिष्ट तत्वों की सरणी बनाना

समस्या विवरण

आकार N, कुल योग SUM, और ऊपरी सीमा K (कोई तत्व K से बड़ा नहीं) दिए गए हैं। सभी तत्व विशिष्ट हों, ऐसी एक सरणी बनाएं। असंभव हो तो -1 वापस करें।

उदाहरण

इनपुट: N = 4, SUM = 16, K = 9

आउटपुट: [1, 2, 4, 9] (योग = 16, सभी ≤9, विशिष्ट)

एल्गोरिदम

1. न्यूनतम संभव योग: min_sum = N*(N+1)/2 (1+2+...+N)
2. अधिकतम संभव योग: max_sum = N*K - N*(N-1)/2 (K, K-1, ...)
3. यदि SUM रेंज से बाहर: -1 वापस करें
4. res = [0, 1, 2, ..., N] इनिशियलाइज़ करें
5. sum = min_sum, i = N
6. जब तक i >= 1:
   • x = sum + (K - i)
   • यदि x < SUM: res[i] = K, sum += K-i, K--
   • अन्यथा: res[i] += SUM - sum, sum = SUM, ब्रेक
   • i--
7. res वापस करें

पायथन कार्यान्वयन

def get_arr(N, SUM, K):
    min_sum = N * (N + 1) // 2
    max_sum = N * K - N * (N - 1) // 2
    if min_sum > SUM or max_sum < SUM:
        return -1
    res = [i for i in range(N + 1)]
    sum_val = min_sum
    i = N
    while i >= 1:
        x = sum_val + (K - i)
        if x < SUM:
            sum_val += (K - i)
            res[i] = K
            K -= 1
        else:
            res[i] += (SUM - sum_val)
            sum_val = SUM
            break
        i -= 1
    return res

N, SUM, K = 4, 16, 9
print(get_arr(N, SUM, K))

इनपुट

4, 16, 9

आउटपुट

[0, 1, 2, 4, 9]

नोट

आउटपुट में इंडेक्स 0 पर 0 आता है (1-आधारित इंडेक्सिंग के कारण)। वास्तविक सरणी res[1:] है: [1, 2, 4, 9]।