Check if a large number can be divided into two or more segments of equal sum | C ++ program to Check if a large number can be divided into two or more segments of equal sum ; Function to check if a number can be divided into segments ; length of string ; array to store prefix sum ; first index ; calculate the prefix ; iterate for all number from second number ; sum from 0 th index to i - 1 th index ; counter turns true when sum is obtained from a segment ; iterate till the last number ; sum of segments ; if segment sum is equal to first segment ; when greater than not possible ; if at the end all values are traversed and all segments have sum equal to first segment then it is possible ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool check ( string s ) { int n = s . length ( ) ; int Presum [ n ] ; Presum [ 0 ] = s [ 0 ] - '0' ; for ( int i = 1 ; i < n ; i ++ ) { Presum [ i ] = Presum [ i - 1 ] + ( s [ i ] - '0' ) ; } for ( int i = 1 ; i <= n - 1 ; i ++ ) { int sum = Presum [ i - 1 ] ; int presum = 0 ; int it = i ; int flag = 0 ; while ( it < n ) { presum += s [ it ] - '0' ; if ( presum == sum ) { presum = 0 ; flag = 1 ; } else if ( presum > sum ) { break ; } it ++ ; } if ( presum == 0 && it == n && flag == 1 ) { return true ; } } return false ; } int main ( ) { string s = "73452" ; if ( check ( s ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }