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 segmentsbool 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 Codeint 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 sumpublic 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 segmentsdef 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 Codes = "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(N2)
- 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Find More on to that Topic: geeksforgeeks.org/check-if-a-large-number-can-be-divided-into-two-or-more-segments-of-equal-sum/ […]