C++ में K से विभाज्य उपसरणी योग

मान लीजिए हमारे पास पूर्णांकों की एक सरणी A है। हमें सन्निकट गैर-खाली उपसरणी की संख्या ढूंढनी है जिनका योग k से विभाज्य है। यदि A = [4,5,0,-2,-3,1] और k = 5 है, तो आउटपुट 7 होगा। सात उपसरणी हैं: [[4,5,0,-2,-3,1], [5], [5,0],[5,0,-2,-3], [0], [0,-2,-3], [-2,-3]]

हल करने के चरण

• एक मैप m बनाएं और m[0] को 1 सेट करें
• temp := 0, ans := 0, और n := सरणी a का आकार
• i को 0 से n-1 तक लूप करें
  • temp := temp + a[i]
  • x := (temp % k + k) % k
  • ans := ans + m[x]
  • m[x] को 1 से बढ़ाएं
• ans वापस करें

उदाहरण

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int subarraysDivByK(vector<int>& a, int k) {       unordered_map <int, int> m;       m[0] = 1;       int temp = 0;       int ans = 0;       int n = a.size();       for(int i = 0; i < n; i++){          temp += a[i];          int x = (temp % k + k) % k;          ans += m[x];          m[x]++;       }       return ans;    } }; main(){    vector<int> v = {4,5,0,-2,-3,1};    Solution ob;    cout <<(ob.subarraysDivByK(v, 5)); }

इनपुट

[4,5,0,-2,-3,1] 5

आउटपुट

7