পাইথনে লিস্টের সব সাবসিকোয়েন্সের_WIDTH_র যোগফল (Mod 10^9+7)

একটি সংখ্যার লিস্ট nums দেওয়া আছে। একটি সিকোয়েন্সের Width = সেটার সর্বোচ্চ মান - সর্বনিম্ন মান। nums-এর সব সাবসিকোয়েন্সের Width-এর যোগফল বের করতে হবে। ফলাফল বড় হলে 10^9+7 দিয়ে মডুলো।

উদাহরণ: nums = [7, 4, 9] → সাবসিকোয়েন্স: [7],[4],[9],[7,4],[7,9],[4,9],[7,4,9]। Width: 0,0,0,3,2,5,5 → যোগফল 15।

সমাধানের ধাপসমূহ (গাণিতিক ফর্মুলা + সর্টিং)

1. nums সর্ট করুন।

2. প্রতিটি ইন্ডেক্স i এর জন্য, nums[i] কতবার Max হিসেবে এবং কতবার Min হিসেবে আসে তা বের করুন।

3. power[i] = 2^i % MOD প্রিক্যালকুলেট করুন।

4. positive = (power[i] - 1) * nums[i] (Max হিসেবে কন্ট্রিবিউশন)।

5. negative = (power[n-i-1] - 1) * nums[i] (Min হিসেবে কন্ট্রিবিউশন)।

6. ans = (ans + positive - negative) % MOD।

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

class Solution:
    def solve(self, nums):
        m = 10**9 + 7
        nums.sort()
        ans = 0
        power = [1] * (len(nums) + 1)
        for i in range(1, len(nums) + 1):
            power[i] = power[i - 1] * 2 % m
        for i in range(len(nums)):
            positive = (power[i] - 1) * nums[i]
            negative = (power[len(nums) - i - 1] - 1) * nums[i]
            ans = (ans + positive - negative) % m
        return ans

ob = Solution()
nums = [7, 4, 9]
print(ob.solve(nums))

ইনপুট

[7, 4, 9]

আউটপুট

15