सी ++ में बाद की चौड़ाई का योग

मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी ए है, ए के सभी गैर-रिक्त अनुक्रमों पर विचार करें। किसी भी अनुक्रम एस के लिए, एस की चौड़ाई को एस के अधिकतम और न्यूनतम तत्व के बीच का अंतर मानें। हमें चौड़ाई का योग खोजना होगा ए के बाद के सभी उत्तर। उत्तर बहुत बड़ा हो सकता है, इसलिए उत्तर मॉड्यूलो 10^9 + 7 लौटाएं।

इसलिए, यदि इनपुट [3,1,2] जैसा है, तो आउटपुट 6 होगा, ऐसा इसलिए है क्योंकि इसके बाद के क्रम [1], [2], [3], [2,1], [2] हैं। 3], [1,3], [2,1,3] और चौड़ाई 0, 0, 0, 1, 1, 2, 2 हैं, इसलिए चौड़ाई मानों का योग 6 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन ऐड () को परिभाषित करें, इसमें a, b,

  . लगेगा

• वापसी ((एक मॉड एम) + (बी मॉड एम)) मॉड एम

• एक फ़ंक्शन उप () को परिभाषित करें, इसमें a, b,

  . लगेगा

• वापसी (((एक मॉड एम) - (बी मॉड एम)) + एम) मॉड एम

• फ़ंक्शन mul() को परिभाषित करें, इसमें a, b,

  . लगेगा

• वापसी ((एक मॉड एम) * (बी मॉड एम)) मॉड एम

• मुख्य विधि से, निम्न कार्य करें -

• सरणी को क्रमबद्ध करें a

• उत्तर:=0

• n :=आकार का

• आरसीएनटी:=1

• इनिशियलाइज़ i :=0 के लिए, जब i

  • x =mul(a[i], sub(rcnt, 1))

  • y =mul(a[n-1-i], sub(rcnt, 1))

  • उत्तर =जोड़ें (उत्तर, उप (एक्स, वाई))

  • आरसीएनटी =आरसीएनटी * 2

  • आरसीएनटी:=आरसीएनटी मॉड एम

• वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,1,2};
   cout << (ob.sumSubseqWidths(v));
}

इनपुट

{3,1,2}

आउटपुट

6