Check if a large number can be divided into two or more segments of equal sum

0 0 7 minutes read

Given a very large Number N. The task is to check if the number can be divided into two or more segments of an equal sum.

Examples:

Input: N = 73452  
Output: Yes
Segments of {7}, {3, 4}, {5, 2} which has equal sum of 7

Input: N = 1248
Output: No

The following steps can be followed to solve the problem:

Since the number can be large, the number is initialized in a string.
Use prefixSum array to store the prefix sum of the array.
Now traverse from the second element to last, and the first segment thus will be 0 to i-1, whose sum is Prefixsum[i-1].
Use another pointer that traverses from i to n, and keep adding the sum.
If the sum at any stage is equal to Prefixsum[i-1], then the segment has a sum equal to first.
Reinitialize the segment sum value to 0 and keep moving the pointer.
If at any stage the segment sum exceeds the sum of the first segment, then break, as the division with segment sum as prefixsum[i-1] is not possible.
If the pointer reaches the last number, check if the last segment sum is equal to the first segment sum i.e., prefixsum[i-1], then it can be divided into segments of the equal sum.

Implementation:

C++

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

Java

// Java program to Check if a large number can be divided 
// into two or more segments of equal sum
 
public class GFG {
 
    // Function to check if a number
    // can be divided into segments
    static boolean check(String s)
    {
        // length of string
        int n = s.length();
      
        // array to store prefix sum
        int[] Presum = new int[n];
      
        // first index
        char[] s1 = s.toCharArray();
        Presum[0] = s1[0] - '0';
      
        // calculate the prefix
        for (int i = 1; i < n; i++) {
            Presum[i] = Presum[i - 1] + (s1[i] - '0');
        }
      
        // iterate for all number from second number
        for (int i = 1; i <= n - 1; i++) {
      
            // sum from 0th index to i-1th index
            int sum = Presum[i - 1];
            int presum = 0;
            int it = i;
      
            // counter turns true when sum
            // is obtained from a segment
            int flag = 0;
      
            // iterate till the last number
            while (it < n) {
                // sum of segments
                presum += s1[it] - '0';
      
                // if segment sum is equal
                // to first segment
                if (presum == sum) {
                    presum = 0;
                    flag = 1;
                }
                // when greater than not possible
                else if (presum > sum) {
                    break;
                }
                it++;
            }
      
            // if at the end all values are traversed
            // and all segments have sum equal to first segment
            // then it is possible
            if (presum == 0 && it == n && flag == 1) {
                return true;
            }
        }
        return false;
    }
      
    // Driver Code
    public static void main(String[] args) {
         
        String s = "73452";
        if (check(s))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

Python3

# Python 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
def check(s):
    # length of string
    n = len(s)
    # list to store prefix sum
    Presum = [0] * n
    # calculate the first prefix sum
    Presum[0] = int(s[0])
    # calculate the prefix sum for rest of the numbers
    for i in range(1, n):
        Presum[i] = Presum[i - 1] + int(s[i])
    # iterate for all numbers from second number
    for i in range(1, n - 1):
        # sum from 0th index to i-1th index
        sum = Presum[i - 1]
        # temporary sum
        presum = 0
        # iterator for checking all segments
        it = i
        # counter to check if sum is obtained from a segment
        flag = 0
        # iterate till the last number
        while it < n:
            # sum of segments
            presum += int(s[it])
            # if segment sum is equal to first segment sum
            if presum == sum:
                # reset the temporary sum
                presum = 0
                # set the flag to indicate segment sum is obtained
                flag = 1
            # when greater than first segment sum not possible
            elif presum > sum:
                break
            # move to next number
            it += 1
        # if all values are traversed and all segments have sum equal to first segment
        # then it is possible
        if presum == 0 and it == n and flag == 1:
            return True
    # if not possible
    return False
 
# Driver Code
s = "73452"
if check(s):
    print("Yes")
else:
    print("No")

C#

// C# program to Check if a large
// number can be divided into two
// or more segments of equal sum 
using System;
 
class GFG 
{ 
 
    // Function to check if a number 
    // can be divided into segments 
    static bool check(String s) 
    { 
        // length of string 
        int n = s.Length; 
     
        // array to store prefix sum 
        int[] Presum = new int[n]; 
     
        // first index 
        char[] s1 = s.ToCharArray(); 
        Presum[0] = s1[0] - '0'; 
     
        // calculate the prefix 
        for (int i = 1; i < n; i++) 
        { 
            Presum[i] = Presum[i - 1] + (s1[i] - '0'); 
        } 
     
        // iterate for all number from second number 
        for (int i = 1; i <= n - 1; i++) 
        { 
     
            // sum from 0th index to i-1th index 
            int sum = Presum[i - 1]; 
            int presum = 0; 
            int it = i; 
     
            // counter turns true when sum 
            // is obtained from a segment 
            int flag = 0; 
     
            // iterate till the last number 
            while (it < n) 
            { 
                // sum of segments 
                presum += s1[it] - '0'; 
     
                // if segment sum is equal 
                // to first segment 
                if (presum == sum)
                { 
                    presum = 0; 
                    flag = 1; 
                } 
                 
                // when greater than not possible 
                else if (presum > sum)
                { 
                    break; 
                } 
                it++; 
            } 
     
            // if at the end all values are traversed 
            // and all segments have sum equal to first segment 
            // then it is possible 
            if (presum == 0 && it == n && flag == 1)
            { 
                return true; 
            } 
        } 
        return false; 
    } 
     
    // Driver Code 
    public static void Main(String[] args) 
    { 
         
        String s = "73452"; 
        if (check(s)) 
            Console.WriteLine("Yes"); 
        else
            Console.WriteLine("No"); 
    } 
} 
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
    // Javascript 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
    function check(s)
    {
     
        // length of string
        let n = s.length;
 
        // array to store prefix sum
        var Presum = [];
         
        // first index
        Presum.push(parseInt(s[0]));
 
        // calculate the prefix
        let i;
        for (i = 1; i < n; i++) {
            Presum.push(Presum[i - 1] + parseInt(s[i]));
        }
 
        // iterate for all number from second number
        for (i = 1; i <= n - 1; i++) {
 
            // sum from 0th index to i-1th index
            let sum = Presum[i - 1];
            let presum = 0;
            let it = i;
 
            // counter turns true when sum
            // is obtained from a segment
            let flag = 0;
 
            // iterate till the last number
            while (it < n) {
                // sum of segments
                presum += parseInt(s[it]);
 
                // if segment sum is equal
                // to first segment
                if (presum == sum) {
                    presum = 0;
                    flag = 1;
                }
                // when greater than not possible
                else if (presum > sum) {
                    break;
                }
                it++;
            }
 
            // if at the end all values are traversed
            // and all segments have sum equal to first segment
            // then it is possible
            if (presum == 0 && it == n && flag == 1) {
                return true;
            }
        }
        return false;
    }
     
    // Driver Code
    var s = "73452";
    if (check(s))
        document.write("Yes");
    else
        document.write("No");
         
        // This code is contributed by ajaykrsharma132.
</script>

Output

Yes

Complexity Analysis:

Time Complexity: O(N²)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!