Find the Sub | C ++ program to find subarray with sum closest to 0 ; Sort on the basis of sum ; Returns subarray with sum closest to 0. ; To consider the case of subarray starting from beginning of the array ; Store prefix sum with index ; Sort on the basis of sum ; Find two consecutive elements with minimum difference ; Update minimum difference and starting and ending indexes ; Return starting and ending indexes ; Drivers code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct prefix { int sum ; int index ; } ; bool comparison ( prefix a , prefix b ) { return a . sum < b . sum ; } pair < int , int > findSubArray ( int arr [ ] , int n ) { int start , end , min_diff = INT_MAX ; prefix pre_sum [ n + 1 ] ; pre_sum [ 0 ] . sum = 0 ; pre_sum [ 0 ] . index = -1 ; for ( int i = 1 ; i <= n ; i ++ ) { pre_sum [ i ] . sum = pre_sum [ i - 1 ] . sum + arr [ i - 1 ] ; pre_sum [ i ] . index = i - 1 ; } sort ( pre_sum , pre_sum + ( n + 1 ) , comparison ) ; for ( int i = 1 ; i <= n ; i ++ ) { int diff = pre_sum [ i ] . sum - pre_sum [ i - 1 ] . sum ; if ( min_diff > diff ) { min_diff = diff ; start = pre_sum [ i - 1 ] . index ; end = pre_sum [ i ] . index ; } } pair < int , int > p = make_pair ( start + 1 , end ) ; return p ; } int main ( ) { int arr [ ] = { 2 , 3 , -4 , -1 , 6 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; pair < int , int > point = findSubArray ( arr , n ) ; cout << " Subarray ▁ starting ▁ from ▁ " ; cout << point . first << " ▁ to ▁ " << point . second ; return 0 ; }