পাইথনে অ্যারের সব সাবসেটের ম্যাক্স-মিন পার্থক্যের যোগফল বের করুন

সমস্যা বিবরণ

একটি অ্যারে A দেওয়া আছে (উপাদানগুলোISTINCT নাও হতে পারে)। সব সম্ভাব্য সাবসেটের জন্য max(s) - min(s) এর যোগফল বের করতে হবে। এখানে max(s) এবং min(s) হলো সাবসেট s-এর সর্বোচ্চ ও ন্যূনতম মান।

উদাহরণস্বরূপ, A=[1,3,4] হলে আউটপুট 9।

সমাধানের ধাপসমূহ

1. n = len(A)।
2. A সর্ট করুন।
3. sum_min = 0, sum_max = 0।
4. i = 0 থেকে n-1 পর্যন্ত:
   • sum_max = (2 * sum_max + A[n-1-i]) % MOD।
   • sum_min = (2 * sum_min + A[i]) % MOD।
5. রিটার্ন (sum_max - sum_min + MOD) % MOD। (এখানে MOD = 1000000007)।

পাইথন কোড উদাহরণ

MOD = 1000000007

def get_max_min_diff(A):
    n = len(A)
    A.sort()
    sum_min = 0
    sum_max = 0
    for i in range(n):
        sum_max = (2 * sum_max + A[n-1-i]) % MOD
        sum_min = (2 * sum_min + A[i]) % MOD
    return (sum_max - sum_min + MOD) % MOD

A = [1, 3, 4]
print(get_max_min_diff(A))  # আউটপুট: 9

ইনপুট

[1, 3, 4]

আউটপুট

9