मान लीजिए हमारे पास पूर्णांकों की एक सरणी A है, A के सभी गैर-खाली सबसीक्वेंस पर विचार करें। किसी भी अनुक्रम S के लिए, S की चौड़ाई को S के अधिकतम और न्यूनतम तत्व के बीच का अंतर माना जाता है। हमें A के सभी सबसीक्वेंस की चौड़ाई का योग ढूंढना है। उत्तर बहुत बड़ा हो सकता है, इसलिए मॉड्यूलो 10^9 + 7 में वापस करें।
उदाहरण के लिए, यदि इनपुट [3,1,2] है, तो आउटपुट 6 होगा।
हल करने का दृष्टिकोण
मुख्य अंतर्दृष्टि: प्रत्येक तत्व का योगदान इस पर निर्भर करता है कि यह कितनी बार अधिकतम बनाम न्यूनतम होता है:
सरणी को सॉर्ट करें
सॉर्ट की गई सरणी में, a[i] 2^i बार अधिकतम होता है और 2^(n-1-i) बार न्यूनतम होता है
योगदान = a[i] * (2^i - 2^(n-1-i))
सभी योगदानों को मॉड्यूलो 10^9+7 के साथ जोड़ें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
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;
}
int sumSubseqWidths(vector<int>& a) {
sort(a.begin(), a.end());
int ans = 0;
int 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
