Smallest subarray whose sum is multiple of array size
Given an array of size N, we need to find the smallest subarray whose sum is divisible by array size N.
Examples :
Input : arr[] = [1, 1, 2, 2, 4, 2] Output : [2 4] Size of array, N = 6 Following subarrays have sum as multiple of N [1, 1, 2, 2], [2, 4], [1, 1, 2, 2, 4, 2] The smallest among all is [2 4]
We can solve this problem considering the below facts,
Let S[i] denotes sum of first i elements i.e. S[i] = a[1] + a[2] .. + a[i] Now subarray arr(i, i + x) has sum multiple of N then, (arr(i] + arr[i+1] + .... + arr[i + x])) % N = 0 (S[i+x] – S[i] ) % N = 0 S[i] % N = S[i + x] % N
We need to find the minimum value of x for which the above condition holds. This can be implemented in a single iteration with O(N) time-complexity using another array modIdx of size N. Array modIdx is initialized with all elements as -1. modIdx[k] is to be updated with i in each iteration, where k = sum % N.
Now in each iteration, we need to update modIdx[k] according to the value of sum % N.
We need to check two things,
If at any instant k = 0 and it is the first time we are updating modIdx[0] (i.e. modIdx[0] was -1)
Then we assign x to i + 1, because (i + 1) will be the length of subarray whose sum is multiple of N
In another case whenever we get a mod value, if this index is not -1, that means it is updated by some other sum value, whose index is stored at that index, we update x with this difference value, i.e. by i – modIdx[k].
After each above operation, we update the minimum value of length and corresponding starting index and end index for the subarray. Finally, this gives the solution to our problem.
Implementation:
C++
// C++ program to find subarray whose sum // is multiple of size #include <bits/stdc++.h> using namespace std; // Method prints smallest subarray whose sum is // multiple of size void printSubarrayMultipleOfN( int arr[], int N) { // A direct index table to see if sum % N // has appeared before or not. int modIdx[N]; // initialize all mod index with -1 for ( int i = 0; i < N; i++) modIdx[i] = -1; // initializing minLen and curLen with larger // values int minLen = N + 1; int curLen = N + 1; // To store sum of array elements int sum = 0; // looping for each value of array int l, r; for ( int i = 0; i < N; i++) { sum += arr[i]; sum %= N; // If this is the first time we have // got mod value as 0, then S(0, i) % N // == 0 if (modIdx[sum] == -1 && sum == 0) curLen = i + 1; // If we have reached this mod before then // length of subarray will be i - previous_position if (modIdx[sum] != -1) curLen = i - modIdx[sum]; // choose minimum length as subarray till now if (curLen < minLen) { minLen = curLen; // update left and right indices of subarray l = modIdx[sum] + 1; r = i; } modIdx[sum] = i; } // print subarray for ( int i = l; i <= r; i++) cout << arr[i] << " " ; cout << endl; } // Driver code to test above method int main() { int arr[] = {1, 1, 2, 2, 4, 2}; int N = sizeof (arr) / sizeof ( int ); printSubarrayMultipleOfN(arr, N); return 0; } |
Java
// Java program to find subarray whose sum // is multiple of size class GFG { // Method prints smallest subarray whose sum is // multiple of size static void printSubarrayMultipleOfN( int arr[], int N) { // A direct index table to see if sum % N // has appeared before or not. int modIdx[] = new int [N]; // initialize all mod index with -1 for ( int i = 0 ; i < N; i++) modIdx[i] = - 1 ; // initializing minLen and curLen with // larger values int minLen = N + 1 ; int curLen = N + 1 ; // To store sum of array elements int sum = 0 ; // looping for each value of array int l = 0 , r = 0 ; for ( int i = 0 ; i < N; i++) { sum += arr[i]; sum %= N; // If this is the first time we // have got mod value as 0, then // S(0, i) % N == 0 if (modIdx[sum] == - 1 && sum == 0 ) curLen = i + 1 ; // If we have reached this mod before // then length of subarray will be i // - previous_position if (modIdx[sum] != - 1 ) curLen = i - modIdx[sum]; // choose minimum length as subarray // till now if (curLen < minLen) { minLen = curLen; // update left and right indices // of subarray l = modIdx[sum] + 1 ; r = i; } modIdx[sum] = i; } // print subarray for ( int i = l; i <= r; i++) System.out.print(arr[i] + " " ); System.out.println(); } // Driver program public static void main(String arg[]) { int arr[] = { 1 , 1 , 2 , 2 , 4 , 2 }; int N = arr.length; printSubarrayMultipleOfN(arr, N); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to find subarray # whose sum is multiple of size # Method prints smallest subarray # whose sum is multiple of size def printSubarrayMultipleOfN(arr, N): # A direct index table to see if sum % N # has appeared before or not. modIdx = [ 0 for i in range (N)] # initialize all mod index with -1 for i in range (N): modIdx[i] = - 1 # initializing minLen and curLen # with larger values minLen = N + 1 curLen = N + 1 # To store sum of array elements sum = 0 # looping for each value of array l = 0 ; r = 0 for i in range (N): sum + = arr[i] sum % = N # If this is the first time we have # got mod value as 0, then S(0, i) % N # == 0 if (modIdx[ sum ] = = - 1 and sum = = 0 ): curLen = i + 1 # If we have reached this mod before then # length of subarray will be i - previous_position if (modIdx[ sum ] ! = - 1 ): curLen = i - modIdx[ sum ] # choose minimum length as subarray till now if (curLen < minLen): minLen = curLen # update left and right indices of subarray l = modIdx[ sum ] + 1 r = i modIdx[ sum ] = i # print subarray for i in range (l, r + 1 ): print (arr[i] , " " , end = "") print () # Driver program arr = [ 1 , 1 , 2 , 2 , 4 , 2 ] N = len (arr) printSubarrayMultipleOfN(arr, N) # This code is contributed by Anant Agarwal. |
C#
// C# program to find subarray whose sum // is multiple of size using System; class GFG { // Method prints smallest subarray whose sum is // multiple of size static void printSubarrayMultipleOfN( int []arr, int N) { // A direct index table to see if sum % N // has appeared before or not. int []modIdx = new int [N]; // initialize all mod index with -1 for ( int i = 0; i < N; i++) modIdx[i] = -1; // initializing minLen and curLen with // larger values int minLen = N + 1; int curLen = N + 1; // To store sum of array elements int sum = 0; // looping for each value of array int l = 0, r = 0; for ( int i = 0; i < N; i++) { sum += arr[i]; sum %= N; // If this is the first time we // have got mod value as 0, then // S(0, i) % N == 0 if (modIdx[sum] == -1 && sum == 0) curLen = i + 1; // If we have reached this mod before // then length of subarray will be i // - previous_position if (modIdx[sum] != -1) curLen = i - modIdx[sum]; // choose minimum length as subarray // till now if (curLen < minLen) { minLen = curLen; // update left and right indices // of subarray l = modIdx[sum] + 1; r = i; } modIdx[sum] = i; } // print subarray for ( int i = l; i <= r; i++) Console.Write(arr[i] + " " ); Console.WriteLine(); } // Driver Code public static void Main() { int []arr = {1, 1, 2, 2, 4, 2}; int N = arr.Length; printSubarrayMultipleOfN(arr, N); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to find subarray // whose sum is multiple of size // Method prints smallest subarray // whose sum is multiple of size function printSubarrayMultipleOfN( $arr , $N ) { // A direct index table to see // if sum % N has appeared // before or not. $modIdx = array (); // initialize all mod // index with -1 for ( $i = 0; $i < $N ; $i ++) $modIdx [ $i ] = -1; // initializing minLen and // curLen with larger values $minLen = $N + 1; $curLen = $N + 1; // To store sum of // array elements $sum = 0; // looping for each // value of array $l ; $r ; for ( $i = 0; $i < $N ; $i ++) { $sum += $arr [ $i ]; $sum %= $N ; // If this is the first time // we have got mod value as 0, // then S(0, i) % N == 0 if ( $modIdx [ $sum ] == -1 && $sum == 0) $curLen = $i + 1; // If we have reached this mod // before then length of subarray // will be i - previous_position if ( $modIdx [ $sum ] != -1) $curLen = $i - $modIdx [ $sum ]; // choose minimum length // as subarray till now if ( $curLen < $minLen ) { $minLen = $curLen ; // update left and right // indices of subarray $l = $modIdx [ $sum ] + 1; $r = $i ; } $modIdx [ $sum ] = $i ; } // print subarray for ( $i = $l ; $i <= $r ; $i ++) echo $arr [ $i ] , " " ; echo "\n" ; } // Driver Code $arr = array (1, 1, 2, 2, 4, 2); $N = count ( $arr ); printSubarrayMultipleOfN( $arr , $N ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to find subarray whose sum // is multiple of size // Method prints smallest subarray whose sum is // multiple of size function printSubarrayMultipleOfN(arr, N) { // A direct index table to see if sum % N // has appeared before or not. let modIdx = new Array(N); // initialize all mod index with -1 for (let i = 0; i < N; i++) modIdx[i] = -1; // initializing minLen and curLen with // larger values let minLen = N + 1; let curLen = N + 1; // To store sum of array elements let sum = 0; // looping for each value of array let l = 0, r = 0; for (let i = 0; i < N; i++) { sum += arr[i]; sum %= N; // If this is the first time we // have got mod value as 0, then // S(0, i) % N == 0 if (modIdx[sum] == -1 && sum == 0) curLen = i + 1; // If we have reached this mod before // then length of subarray will be i // - previous_position if (modIdx[sum] != -1) curLen = i - modIdx[sum]; // choose minimum length as subarray // till now if (curLen < minLen) { minLen = curLen; // update left and right indices // of subarray l = modIdx[sum] + 1; r = i; } modIdx[sum] = i; } // print subarray for (let i = l; i <= r; i++) document.write(arr[i] + " " ); document.write( "</br>" ); } let arr = [1, 1, 2, 2, 4, 2]; let N = arr.length; printSubarrayMultipleOfN(arr, N); </script> |
2 4
Time Complexity: O(N)
Auxiliary Space: O(N)