Find a subarray whose sum is divisible by size of the array | C ++ implementation of above approach ; Function to find a subarray whose sum is a multiple of N ; Prefix sum array to store cumulative sum ; Single state dynamic programming relation for prefix sum array ; Generating all sub - arrays ; If the sum of the sub - array [ i : j ] is a multiple of N ; If the function reaches here it means there are no subarrays with sum as a multiple of N ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void CheckSubarray ( int arr [ ] , int N ) { int presum [ N + 1 ] = { 0 } ; for ( int i = 1 ; i <= N ; i += 1 ) { presum [ i ] = presum [ i - 1 ] + arr [ i - 1 ] ; } for ( int i = 1 ; i <= N ; i += 1 ) { for ( int j = i ; j <= N ; j += 1 ) { if ( ( presum [ j ] - presum [ i - 1 ] ) % N == 0 ) { cout << i - 1 << " ▁ " << j - 1 ; return ; } } } cout << -1 ; } int main ( ) { int arr [ ] = { 7 , 5 , 3 , 7 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; CheckSubarray ( arr , N ) ; return 0 ; }