배열이 주어지면 도착[] 그리고 정수 케이 작업은 합계가 다음과 같은 모든 하위 배열을 계산하는 것입니다. 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 모듈로 k 사용
아이디어는 사용하는 것입니다 접두사 합 기법 함께 해싱 . 주의 깊게 살펴보면 하위 배열 arr[i...j]에 k로 나눌 수 있는 합이 있는 경우 (접두사 sum[i] % k)는 (접두사 sum[j] % k)와 동일할 것이라고 말할 수 있습니다. 따라서 해시 맵이나 사전을 유지하면서 arr[]을 반복하여 (접두사 합 mod k)의 수를 계산할 수 있습니다. 각 인덱스 i에 대해 i에서 끝나고 합계를 k로 나눌 수 있는 하위 배열의 수는 i 이전에 (접두사 sum[i] mod k)의 발생 횟수와 같습니다.
메모: (prefix sum mod k)의 음수 값은 다음과 같은 언어에서 별도로 처리해야 합니다. C++ 자바 기음# 그리고 자바스크립트 반면에 파이썬 (접두사 합계 mod 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
시간 복잡도: O(n)은 배열을 한 번만 반복하기 때문입니다.
보조 공간: 최대 O(min(n k)) 케이 키는 해시 맵이나 사전에 존재할 수 있습니다.
자바빈