Comprobar si un número grande se puede dividir en dos o más segmentos de igual suma

Posted on by Rudeus Greyrat

Dado un número N muy grande, la tarea es verificar si el número se puede dividir en dos o más segmentos de una suma igual. 
Ejemplos : 
 

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

Input: N = 1248
Output: No

Se pueden seguir los siguientes pasos para resolver el problema: 
 

  1. Dado que el número puede ser grande, el número se inicializa en una string.
  2. Use la array prefixSum para almacenar la suma del prefijo de la array.
  3. Ahora recorra del segundo elemento al último, y el primer segmento será 0 a i-1, cuya suma es Prefixsum[i-1].
  4. Use otro puntero que atraviese de i an, y siga sumando la suma.
  5. Si la suma en cualquier etapa es igual a Prefixsum[i-1], entonces el segmento tiene una suma igual a la primera.
  6. Reinicialice el valor de la suma del segmento a 0 y siga moviendo el puntero.
  7. Si en cualquier etapa la suma del segmento excede la suma del primer segmento, entonces rompa, ya que la división con la suma del segmento como prefijosum[i-1] no es posible.
  8. Si el puntero alcanza el último número, verifique si la suma del último segmento es igual a la suma del primer segmento, es decir, prefixsum[i-1], entonces se puede dividir en segmentos de igual suma.

A continuación se muestra la implementación del enfoque anterior.
 

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");
    }
}

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>
Producción: 

Yes

 

Tiempo Complejidad: O(N 2 ) 
Espacio Auxiliar: O(N)
 

Publicación traducida automáticamente

Artículo escrito por Striver y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *