সমস্যা বিবরণ
অ্যারে A-এর সব নন-ইম্পটি সাবসিকোয়েন্স বিবেচনা করুন। একটি সিকোয়েন্সের ওয়িডথ = ম্যাক্স - মিন। সব সাবসিকোয়েন্সের ওয়িডথের সমষ্টি বের করতে হবে (মডুলো 10^9+7)।
উদাহরণ
A = [3,1,2] → আউটপুট = 6
সমাধান পদ্ধতি
- অ্যারে সর্ট করুন।
- প্রতিটি এলিমেন্ট a[i] কতবার ম্যাক্স এবং কতবার মিন হয় তা গণনা করুন।
- a[i] ম্যাক্স হয় 2^i বার, মিন হয় 2^(n-1-i) বার।
- উত্তর = Σ a[i] * (2^i - 2^(n-1-i))।
- মডুলার অ্যারিথমেটিক (add, sub, mul) ব্যবহার করা হয়।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
lli add(lli a, lli b) { return ((a % m) + (b % m)) % m; }
lli sub(lli a, lli b) { return (((a % m) - (b % m)) + m) % m; }
lli mul(lli a, lli b) { return ((a % m) * (b % m)) % m; }
public:
int sumSubseqWidths(vector<int>& a) {
sort(a.begin(), a.end());
int ans = 0, n = a.size();
lli rcnt = 1;
for (int i = 0; i < n; i++) {
ans = add(ans, sub(mul(a[i], sub(rcnt, 1)),
mul(a[n-1-i], sub(rcnt, 1))));
rcnt <<= 1;
rcnt %= m;
}
return ans;
}
};
int main() {
Solution ob;
vector<int> v = {3,1,2};
cout << ob.sumSubseqWidths(v);
return 0;
}ইনপুট ও আউটপুট
ইনপুট: {3,1,2}
আউটপুট: 6
