配列が与えられた場合 到着[] そして整数 k タスクは、合計が次の部分配列をすべてカウントすることです。 kで割り切れる 。
例:
入力： arr[] = [4 5 0 -2 -3 1] k = 5
出力： 7
説明： 合計が 5 で割り切れる部分配列が 7 つあります: [4 5 0 -2 -3 1] [5] [5 0] [5 0 -2 -3] [0] [0 -2 -3] および [-2 -3]。入力： arr[] = [2 2 2 2 2 2] k = 2
出力： 21
説明： すべての部分配列の合計は 2 で割り切れます。入力： arr[] = [-1 -3 2] k = 5
出力：
説明： 和が k で割り切れる部分配列はありません。
目次
[素朴なアプローチ] すべての部分配列を反復処理する
アイデアは、すべての可能なサブ配列を反復処理しながら、 kを法とする部分配列の合計 。任意のサブ配列について、サブ配列の剰余 k が 0 になると、カウントが 1 ずつインクリメントされます。すべてのサブ配列を反復した後、カウントが結果として返されます。
C++// C++ Code to Count Subarrays With Sum Divisible By K // by iterating over all possible subarrays #include
// C Code to Count Subarrays With Sum Divisible By K // by iterating over all possible subarrays #include
// 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 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# 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 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));
出力
7
時間計算量: O(n^2) は、部分配列のすべての可能な開始点と終了点を反復処理しているためです。
補助スペース: ○(1)
[想定されるアプローチ] Prefix Sum modulo k を使用する
アイデアは使用することです プレフィックスサム手法 とともに ハッシュ化 。注意深く観察すると、部分配列 arr[i...j] の合計が k で割り切れる場合、(接頭辞 sum[i] % k) は (接頭辞 sum[j] % k) に等しいと言えます。したがって、ハッシュ マップまたは辞書を維持しながら、arr[] を反復処理して (prefix sum mod k) の数をカウントできます。各インデックス i について、i で終わり、合計が k で割り切れるサブ配列の数は、i より前の (prefix sum[i] mod k) の出現数に等しくなります。
シュレヤ・ゴーシャルの最初の夫
注記： (prefix sum mod k) の負の値は、次のような言語では個別に処理する必要があります。 C++ ジャワ C# そして JavaScript 一方、 パイソン (prefix sum mod k) は、次の除数の符号を取るため、常に負ではない値になります。 k 。
C++// C++ Code to Count Subarrays With Sum Divisible By K // using Prefix Sum and Hash map #include
// 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 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# 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 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));
出力
7
時間計算量: 配列を 1 回だけ反復しているため、O(n)。
補助スペース: 最大でも O(min(n k)) k キーはハッシュ マップまたは辞書に存在できます。