Find the index in a circular array from which prefix sum is always non | C ++ program for the above approach ; Function to find the starting index of the given circular array s . t . prefix sum array is non negative ; Stores the sum of the array ; Stores the starting index ; Stores the minimum prefix sum of A [ 0. . i ] ; Traverse the array arr [ ] ; Update the value of sum ; If sum is less than min ; Update the min as the value of prefix sum ; Update in ; Otherwise , no such index is possible ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int startingPoint ( int A [ ] , int N ) { int sum = 0 ; int in = 0 ; int min = INT_MAX ; for ( int i = 0 ; i < N ; i ++ ) { sum += A [ i ] ; if ( sum < min ) { min = sum ; in = i + 1 ; } } if ( sum < 0 ) { return -1 ; } return in % N ; } int main ( ) { int arr [ ] = { 3 , -6 , 7 , -4 , -4 , 6 , -1 } ; int N = ( sizeof ( arr ) / sizeof ( arr [ 0 ] ) ) ; cout << startingPoint ( arr , N ) ; return 0 ; }