logo

TechCodeview

Suskaičiuokite pogrupius, kurių suma dalijasi iš K

Duotas masyvas arr[] ir sveikasis skaičius k užduotis yra suskaičiuoti visus pogrupius, kurių suma yra dalijasi iš k .

Pavyzdžiai:

Įvestis: arr[] = [4 5 0 -2 -3 1] k = 5
Išvestis: 7
Paaiškinimas: Yra 7 pokeriai, kurių suma dalijasi iš 5: [4 5 0 -2 -3 1] [5] [5 0] [5 0 -2 -3] [0] [0 -2 -3] ir [-2 -3].



Įvestis: arr[] = [2 2 2 2 2 2] k = 2
Išvestis: 21
Paaiškinimas: Visos pogrupio sumos dalijasi iš 2.

Įvestis: arr[] = [-1 -3 2] k = 5
Išvestis:
Paaiškinimas: Nėra pogrupio, kurio suma dalytųsi iš k.

Turinio lentelė

stygų masyvas c

[Naivus požiūris] Kartojimas per visas pogrupes

Idėja yra kartoti visus įmanomus pogrupius, išlaikant sekimą subbarray modulo k suma . Jei pogrupio modulio k pogrupis tampa 0, skaičių padidinkite 1. Pakartoję visas pogrupes, grąžinkite skaičių kaip rezultatą.

C++ 
// C++ Code to Count Subarrays With Sum Divisible By K // by iterating over all possible subarrays #include    #include  using namespace std; int subCount(vector<int> &arr int k) {  int n = arr.size() res = 0;     // Iterating over starting indices of subarray  for(int i = 0; i < n; i++) {  int sum = 0;    // Iterating over ending indices of subarray  for(int j = i; j < n; j++) {  sum = (sum + arr[j]) % k;  if(sum == 0)  res += 1;  }  }  return res; } int main() {  vector<int> arr = {4 5 0 -2 -3 1};  int k = 5;    cout << subCount(arr k); }
C 
// C Code to Count Subarrays With Sum Divisible By K // by iterating over all possible subarrays #include  int subCount(int arr[] int n int k) {  int res = 0;  // Iterating over starting indices of subarray  for (int i = 0; i < n; i++) {  int sum = 0;  // Iterating over ending indices of subarray  for (int j = i; j < n; j++) {  sum = (sum + arr[j]) % k;  if (sum == 0)  res += 1;  }  }  return res; } int main() {  int arr[] = {4 5 0 -2 -3 1};  int k = 5;  int n = sizeof(arr) / sizeof(arr[0]);  printf('%d' subCount(arr n k));  return 0; }
Java 
// Java Code to Count Subarrays With Sum Divisible By K // by iterating over all possible subarrays import java.util.*; class GfG {  static int subCount(int[] arr int k) {  int n = arr.length res = 0;  // Iterating over starting indices of subarray  for (int i = 0; i < n; i++) {  int sum = 0;  // Iterating over ending indices of subarray  for (int j = i; j < n; j++) {  sum = (sum + arr[j]) % k;  if (sum == 0)  res += 1;  }  }  return res;  }  public static void main(String[] args) {  int[] arr = {4 5 0 -2 -3 1};  int k = 5;  System.out.println(subCount(arr k));  } }
Python 
# Python Code to Count Subarrays With Sum Divisible By K # by iterating over all possible subarrays def subCount(arr k): n = len(arr) res = 0 # Iterating over starting indices of subarray for i in range(n): sum = 0 # Iterating over ending indices of subarray for j in range(i n): sum = (sum + arr[j]) % k if sum == 0: res += 1 return res if __name__ == '__main__': arr = [4 5 0 -2 -3 1] k = 5 print(subCount(arr k))
C# 
// C# Code to Count Subarrays With Sum Divisible By K // by iterating over all possible subarrays using System; using System.Collections.Generic; class GfG {   static int subCount(int[] arr int k) {  int n = arr.Length res = 0;  // Iterating over starting indices of subarray  for (int i = 0; i < n; i++) {  int sum = 0;  // Iterating over ending indices of subarray  for (int j = i; j < n; j++) {  sum = (sum + arr[j]) % k;  if (sum == 0)  res += 1;  }  }  return res;  }  static void Main() {  int[] arr = { 4 5 0 -2 -3 1 };  int k = 5;  Console.WriteLine(subCount(arr k));  } }
JavaScript 
// JavaScript Code to Count Subarrays With Sum Divisible By K // by iterating over all possible subarrays function subCount(arr k) {  let n = arr.length res = 0;  // Iterating over starting indices of subarray  for (let i = 0; i < n; i++) {  let sum = 0;  // Iterating over ending indices of subarray  for (let j = i; j < n; j++) {  sum = (sum + arr[j]) % k;  if (sum === 0)  res += 1;  }  }  return res; } // Driver Code let arr = [4 5 0 -2 -3 1]; let k = 5; console.log(subCount(arr k));

Išvestis 
7

Laiko sudėtingumas: O(n^2), kai kartojame visus galimus posistemių pradžios ir pabaigos taškus.
Pagalbinė erdvė: O(1)

[Numatomas metodas] Naudojant priešdėlį Sum modulo k

Idėja yra naudoti Priešdėlio sumos technika kartu su Maiša . Atidžiai stebėdami galime pasakyti, kad jei pogrupio masyvo [i...j] suma dalijasi iš k, tada (priešdėlis sum[i] % k) bus lygus (priešdėlis suma[j] % k). Taigi galime kartoti per arr[], išlaikydami maišos žemėlapį arba žodyną, kad suskaičiuotume skaičių (priešdėlis sum mod k). Kiekvienam indeksui i posistemių, kurios baigiasi i ir kurių suma dalijasi iš k, skaičius bus lygus (priešdėlis sum[i] mod k) įvykių skaičiui prieš i.

Pastaba: Neigiama reikšmė (priešdėlis sum mod k) turi būti tvarkoma atskirai tokiomis kalbomis kaip C++ Java C# ir JavaScript tuo tarpu in Python (priešdėlis sum mod k) visada yra neneigiama reikšmė, nes ji užima daliklio ženklą, kuris yra k .

C++ 
// C++ Code to Count Subarrays With Sum Divisible By K // using Prefix Sum and Hash map #include    #include  #include  using namespace std; int subCount(vector<int> &arr int k) {  int n = arr.size() res = 0;  unordered_map<int int> prefCnt;  int sum = 0;    // Iterate over all ending points  for(int i = 0; i < n; i++) {    // prefix sum mod k (handling negative prefix sum)  sum = ((sum + arr[i]) % k + k) % k;    // If sum == 0 then increment the result by 1  // to count subarray arr[0...i]  if(sum == 0)  res += 1;    // Add count of all starting points for index i  res += prefCnt[sum];    prefCnt[sum] += 1;  }  return res; } int main() {  vector<int> arr = {4 5 0 -2 -3 1};  int k = 5;    cout << subCount(arr k); }
Java 
// Java Code to Count Subarrays With Sum Divisible By K // using Prefix Sum and Hash map import java.util.*; class GfG {  static int subCount(int[] arr int k) {  int n = arr.length res = 0;  Map<Integer Integer> prefCnt = new HashMap<>();  int sum = 0;  // Iterate over all ending points  for (int i = 0; i < n; i++) {  // prefix sum mod k (handling negative prefix sum)  sum = ((sum + arr[i]) % k + k) % k;  // If sum == 0 then increment the result by 1  // to count subarray arr[0...i]  if (sum == 0)  res += 1;  // Add count of all starting points for index i  res += prefCnt.getOrDefault(sum 0);  prefCnt.put(sum prefCnt.getOrDefault(sum 0) + 1);  }  return res;  }  public static void main(String[] args) {  int[] arr = {4 5 0 -2 -3 1};  int k = 5;  System.out.println(subCount(arr k));  } }
Python 
# Python Code to Count Subarrays With Sum Divisible By K # using Prefix Sum and Dictionary from collections import defaultdict def subCount(arr k): n = len(arr) res = 0 prefCnt = defaultdict(int) sum = 0 # Iterate over all ending points for i in range(n): sum = (sum + arr[i]) % k # If sum == 0 then increment the result by 1 # to count subarray arr[0...i] if sum == 0: res += 1 # Add count of all starting points for index i res += prefCnt[sum] prefCnt[sum] += 1 return res if __name__ == '__main__': arr = [4 5 0 -2 -3 1] k = 5 print(subCount(arr k))
C# 
// C# Code to Count Subarrays With Sum Divisible By K // using Prefix Sum and Hash map using System; using System.Collections.Generic; class GfG {  static int SubCount(int[] arr int k) {  int n = arr.Length res = 0;  Dictionary<int int> prefCnt = new Dictionary<int int>();  int sum = 0;  // Iterate over all ending points  for (int i = 0; i < n; i++) {    // prefix sum mod k (handling negative prefix sum)  sum = ((sum + arr[i]) % k + k) % k;  // If sum == 0 then increment the result by 1  // to count subarray arr[0...i]  if (sum == 0)  res += 1;  // Add count of all starting points for index i  if (prefCnt.ContainsKey(sum))  res += prefCnt[sum];  if (prefCnt.ContainsKey(sum))  prefCnt[sum] += 1;  else  prefCnt[sum] = 1;  }  return res;  }  static void Main() {  int[] arr = { 4 5 0 -2 -3 1 };  int k = 5;  Console.WriteLine(SubCount(arr k));  } }
JavaScript 
// JavaScript Code to Count Subarrays With Sum Divisible By K // using Prefix Sum and Hash map function subCount(arr k) {  let n = arr.length res = 0;  let prefCnt = new Map();  let sum = 0;  // Iterate over all ending points  for (let i = 0; i < n; i++) {  // prefix sum mod k (handling negative prefix sum)  sum = ((sum + arr[i]) % k + k) % k;  // If sum == 0 then increment the result by 1  // to count subarray arr[0...i]  if (sum === 0)  res += 1;  // Add count of all starting points for index i  res += (prefCnt.get(sum) || 0);  prefCnt.set(sum (prefCnt.get(sum) || 0) + 1);  }  return res; } // Driver Code let arr = [4 5 0 -2 -3 1]; let k = 5; console.log(subCount(arr k));

Išvestis 
7

Laiko sudėtingumas: O(n), nes masyve kartojame tik vieną kartą.
Pagalbinė erdvė: O(min(n k)) kaip daugiausia k raktai gali būti maišos žemėlapyje arba žodyne.

java atidaro failą


Sukurti viktoriną