Dividir un número en dos partes divisibles

Dado un número (como una string) y dos enteros a y b, divida la string en dos partes no vacías de modo que la primera parte sea divisible por a y la segunda parte sea divisible por b. Si la string no se puede dividir en dos partes no vacías, emita «NO», de lo contrario, imprima «SÍ» con las dos partes.

Ejemplos: 

Entrada: str = “123”, a = 12, b = 3
Salida: YES
             12 3
Explicación: “12” es divisible por a y “3” es divisible por b. 

Entrada: str = “1200”, a = 4, b = 3
Salida:
             12 00

Entrada: str = “125”, a = 12, b = 3
Salida: NO

Una solución simple es una array de partición uno por uno alrededor de todos los puntos. Para cada partición, verifique si la izquierda y la derecha son divisibles por a y b respectivamente. En caso afirmativo, imprima las partes izquierda y derecha y devuélvalas.

Una solución eficiente es realizar un preprocesamiento y guardar el módulo de división por ‘a’ escaneando la string de izquierda a derecha y el módulo de división por ‘b’ de derecha a izquierda.

Si conocemos el resto del prefijo de 0 a i, cuando se divide por a, entonces calculamos el resto del prefijo de 0 a i+1 usando la siguiente fórmula. 
lr[i+1] = (lr[i]*10 + str[i] -‘0’)%a. 

De la misma manera, el módulo por b se puede encontrar escaneando de derecha a izquierda. Creamos otro rl[] para almacenar restos con b de derecha a izquierda.

Una vez que hemos calculado previamente dos residuos, podemos encontrar fácilmente el punto que divide la string en dos partes.

Implementación:

C++

// C++ program to check if a string can be splitted
// into two strings such that one is divisible by 'a'
// and other is divisible by 'b'.
#include <bits/stdc++.h>
using namespace std;
 
// Finds if it is possible to partition str
// into two parts such that first part is
// divisible by a and second part is divisible
// by b.
void findDivision(string &str, int a, int b)
{
    int len = str.length();
 
    // Create an array of size len+1 and initialize
    // it with 0.
    // Store remainders from left to right when
    // divided by 'a'
    vector<int> lr(len+1, 0);
    lr[0] = (str[0] - '0')%a;
    for (int i=1; i<len; i++)
        lr[i] = ((lr[i-1]*10)%a + (str[i]-'0'))%a;
 
    // Compute remainders from right to left when
    // divided by 'b'
    vector<int> rl(len+1, 0);
    rl[len-1] = (str[len-1] - '0')%b;
    int power10 = 10;
    for (int i= len-2; i>=0; i--)
    {
        rl[i] = (rl[i+1] + (str[i]-'0')*power10)%b;
        power10 = (power10 * 10) % b;
    }
 
    // Find a point that can partition a number
    for (int i=0; i<len-1; i++)
    {
        // If split is not possible at this point
        if (lr[i] != 0)
            continue;
 
        // We can split at i if one of the following
        // two is true.
        // a) All characters after str[i] are 0
        // b) String after str[i] is divisible by b, i.e.,
        //    str[i+1..n-1] is divisible by b.
        if (rl[i+1] == 0)
        {
            cout << "YES\n";
            for (int k=0; k<=i; k++)
                cout << str[k];
 
            cout << ", ";
 
            for (int k=i+1; k<len; k++)
                cout << str[k];
            return;
        }
    }
 
    cout << "NO\n";
}
 
// Driver code
int main()
{
    string str = "123";
    int a = 12, b = 3;
    findDivision(str, a, b);
    return 0;
}

Java

// Java program to check if a string can be splitted
// into two strings such that one is divisible by 'a'
// and other is divisible by 'b'.
class GFG
{
     
// Finds if it is possible to partition str
// into two parts such that first part is
// divisible by a and second part is divisible
// by b.
static void findDivision(String str, int a, int b)
{
    int len = str.length();
 
    // Create an array of size len+1 and initialize
    // it with 0.
    // Store remainders from left to right when
    // divided by 'a'
    int[] lr = new int[len + 1];
     
    lr[0] = ((int)str.charAt(0) - (int)'0')%a;
    for (int i = 1; i < len; i++)
        lr[i] = ((lr[i - 1] * 10) % a +
                ((int)str.charAt(i)-(int)'0')) % a;
 
    // Compute remainders from right to left when
    // divided by 'b'
    int[] rl = new int[len + 1];
    rl[len - 1] = ((int)str.charAt(len - 1) -
                            (int)'0') % b;
    int power10 = 10;
    for (int i= len - 2; i >= 0; i--)
    {
        rl[i] = (rl[i + 1] + ((int)str.charAt(i) -
                        (int)'0') * power10) % b;
        power10 = (power10 * 10) % b;
    }
 
    // Find a point that can partition a number
    for (int i = 0; i < len - 1; i++)
    {
        // If split is not possible at this point
        if (lr[i] != 0)
            continue;
 
        // We can split at i if one of the following
        // two is true.
        // a) All characters after str.charAt(i] are 0
        // b) String after str.charAt(i] is divisible by b, i.e.,
        // str.charAt(i+1..n-1] is divisible by b.
        if (rl[i + 1] == 0)
        {
            System.out.println("YES");
            for (int k = 0; k <= i; k++)
                System.out.print(str.charAt(k));
 
            System.out.print(", ");
 
            for (int k = i + 1; k < len; k++)
                System.out.print(str.charAt(k));
            return;
        }
    }
    System.out.println("NO");
}
 
// Driver code
public static void main (String[] args)
{
    String str = "123";
    int a = 12, b = 3;
    findDivision(str, a, b);
}
}
 
// This code is contributed by mits

Python3

# Python3 program to check if a can be splitted
# into two strings such that one is divisible by 'a'
# and other is divisible by 'b'.
 
# Finds if it is possible to partition str
# into two parts such that first part is
# divisible by a and second part is divisible
# by b.
def findDivision(str, a, b):
    lenn = len(str)
     
    # Create an array of size lenn+1 and
    # initialize it with 0.
    # Store remainders from left to right
    # when divided by 'a'
    lr = [0] * (lenn + 1)
    lr[0] = (int(str[0]))%a
    for i in range(1, lenn):
        lr[i] = ((lr[i - 1] * 10) % a + \
                     int(str[i])) % a
                      
    # Compute remainders from right to left
    # when divided by 'b'
    rl = [0] * (lenn + 1)
    rl[lenn - 1] = int(str[lenn - 1]) % b
    power10 = 10
    for i in range(lenn - 2, -1, -1):
        rl[i] = (rl[i + 1] + int(str[i]) * power10) % b
        power10 = (power10 * 10) % b
         
    # Find a point that can partition a number
    for i in range(0, lenn - 1):
         
        # If split is not possible at this point
        if (lr[i] != 0):
            continue
             
        # We can split at i if one of the following
        # two is true.
        # a) All characters after str[i] are 0
        # b) after str[i] is divisible by b, i.e.,
        # str[i+1..n-1] is divisible by b.
        if (rl[i + 1] == 0):
            print("YES")
            for k in range(0, i + 1):
                print(str[k], end = "")
             
            print(",", end = " ")
             
            for i in range(i + 1, lenn):
                print(str[k], end = "")
                return
     
    print("NO")
 
# Driver code
str = "123"
a, b = 12, 3
findDivision(str, a, b)
 
# This code is contributed by SHUBHAMSINGH10

C#

// C# program to check if a string can be splitted
// into two strings such that one is divisible by 'a'
// and other is divisible by 'b'.
using System;
 
class GFG
{
     
// Finds if it is possible to partition str
// into two parts such that first part is
// divisible by a and second part is divisible
// by b.
static void findDivision(string str, int a, int b)
{
    int len = str.Length;
 
    // Create an array of size len+1 and initialize
    // it with 0.
    // Store remainders from left to right when
    // divided by 'a'
    int[] lr = new int[len + 1];
    lr[0] = ((int)str[0] - (int)'0')%a;
     
    for (int i = 1; i < len; i++)
        lr[i] = ((lr[i - 1] * 10) % a +
                ((int)str[i] - (int)'0')) % a;
 
    // Compute remainders from right to left when
    // divided by 'b'
    int[] rl = new int[len + 1];
    rl[len - 1] = ((int)str[len - 1] - (int)'0') % b;
     
    int power10 = 10;
    for (int i= len - 2; i >= 0; i--)
    {
        rl[i] = (rl[i + 1] + ((int)str[i] -
                (int)'0') * power10) % b;
        power10 = (power10 * 10) % b;
    }
 
    // Find a point that can partition a number
    for (int i = 0; i < len - 1; i++)
    {
        // If split is not possible at this point
        if (lr[i] != 0)
            continue;
 
        // We can split at i if one of the following
        // two is true.
        // a) All characters after str[i] are 0
        // b) String after str[i] is divisible by b, i.e.,
        // str[i+1..n-1] is divisible by b.
        if (rl[i + 1] == 0)
        {
            Console.WriteLine("YES");
            for (int k = 0; k <= i; k++)
                Console.Write(str[k]);
 
            Console.Write(", ");
 
            for (int k = i + 1; k < len; k++)
                Console.Write(str[k]);
            return;
        }
    }
    Console.WriteLine("NO");
}
 
// Driver code
static void Main()
{
    string str = "123";
    int a = 12, b = 3;
    findDivision(str, a, b);
}
}
 
// This code is contributed by mits

Javascript

<script>
 
// js program to check if a string can be splitted
// into two strings such that one is divisible by 'a'
// and other is divisible by 'b'.
 
// Finds if it is possible to partition str
// into two parts such that first part is
// divisible by a and second part is divisible
// by b.
function findDivision(str, a, b)
{
    let len = str.length;
 
    // Create an array of size len+1 and initialize
    // it with 0.
    // Store remainders from left to right when
    // divided by 'a'
    let lr= [];
    for(let i = 0;i<len+1;i++)
        lr.push(0);
    lr[0] = (str[0] - '0')%a;
    for (let i=1; i<len; i++)
        lr[i] = ((lr[i-1]*10)%a + (str.charCodeAt(i)))%a;
 
    // Compute remainders from right to left when
    // divided by 'b'
    let rl= [];
    for(let i = 0;i<len+1;i++)
        rl.push(0);
    rl[len-1] = (str.charCodeAt(len-1))%b;
    let power10 = 10;
    for (let i= len-2; i>=0; i--)
    {
        rl[i] = (rl[i+1] + (str.charCodeAt(i))*power10)%b;
        power10 = (power10 * 10) % b;
    }
 
    // Find a point that can partition a number
    for (let i=0; i<len-1; i++)
    {
        // If split is not possible at this point
        if (lr[i] != 0)
            continue;
 
        // We can split at i if one of the following
        // two is true.
        // a) All characters after str[i] are 0
        // b) String after str[i] is divisible by b, i.e.,
        //    str[i+1..n-1] is divisible by b.
        if (rl[i+1] == 0)
        {
            document.write("YES<br>");
            for (let k=0; k<=i; k++)
                document.write(str[k]);
 
            document.write(", ");
 
            for (let k=i+1; k<len; k++)
                document.write(str[k]);
            return;
        }
    }
 
    document.write( "NO<br>");
}
 
// Driver code
    let str = "123";
    let a = 12, b = 3;
    findDivision(str, a, b);
 
</script>
Producción

YES
12, 3

Complejidad de tiempo: O(n) donde n es la longitud de la string de números de entrada.
Espacio Auxiliar: O(n) 

Otro enfoque: (usando la función incorporada)

Este problema también se puede resolver utilizando funciones de biblioteca integradas para convertir strings en enteros y enteros en strings .

A continuación se muestra la implementación de la idea anterior:

C++

// C++ program to check if a string can be splitted
// into two strings such that one is divisible by 'a'
// and other is divisible by 'b'.
#include <bits/stdc++.h>
using namespace std;
 
// Finds if it is possible to partition str
// into two parts such that first part is
// divisible by a and second part is divisible
// by b.
string findDivision(string S, int a, int b)
{
    for (int i = 0; i < S.size() - 1; i++) {
 
        string firstPart = S.substr(0, i + 1);
        string secondPart = S.substr(i + 1);
 
        if (stoi(firstPart) % a == 0
            and stoi(secondPart) % b == 0)
            return firstPart + " " + secondPart;
    }
    return "-1";
}
 
// Driver code
int main()
{
    string str = "125";
    int a = 12, b = 3;
    string result = findDivision(str, a, b);
 
    if (result == "-1") {
        cout << "NO" << endl;
    }
    else {
        cout << "YES" << endl;
        cout << result << endl;
    }
 
    return 0;
}
 
// This code is contributed by Ishan Khandelwal

Java

// Java program to check if a string can be splitted
// into two strings such that one is divisible by 'a'
// and other is divisible by 'b'.
public class GFG
{
 
  // Finds if it is possible to partition str
  // into two parts such that first part is
  // divisible by a and second part is divisible
  // by b.
  public static String findDivision(String S, int a,
                                    int b)
  {
    for (int i = 0; i < S.length() - 1; i++) {
 
      String firstPart = S.substring(0, i + 1);
      String secondPart = S.substring(i + 1);
 
      if (Integer.parseInt(firstPart) % a == 0
          && Integer.parseInt(secondPart) % b == 0) {
        return firstPart + " " + secondPart;
      }
    }
    return "-1";
  }
 
  // Driver code
  public static void main(String[] args)
  {
    String str = "125";
    int a = 12;
    int b = 3;
    String result = findDivision(str, a, b);
 
    if (result.equals("-1")) {
      System.out.print("NO");
      System.out.print("\n");
    }
    else {
      System.out.print("YES");
      System.out.print("\n");
      System.out.print(result);
      System.out.print("\n");
    }
  }
}
 
// This code is contributed by Aarti_Rathi

Python3

# Python program to check if a string can be splitted
# into two strings such that one is divisible by 'a'
# and other is divisible by 'b'.
 
# Finds if it is possible to partition str
# into two parts such that first part is
# divisible by a and second part is divisible
# by b.
def findDivision(S, a, b):
 
    for i in range(len(S)-1):
 
        firstPart = S[0: i + 1]
        secondPart = S[i + 1:]
 
        if (int(firstPart) % a == 0
            and int(secondPart) % b == 0):
            return firstPart + " " + secondPart
 
    return "-1"
 
# Driver code
Str = "125"
a,b = 12,3
result = findDivision(Str, a, b)
 
if (result == "-1"):
    print("NO")
 
else:
    print("YES")
    print(result)
 
# This code is contributed by shinjanpatra

C#

// C# program to check if a string can be splitted
// into two strings such that one is divisible by 'a'
// and other is divisible by 'b'.
using System;
using System.Collections.Generic;
 
public class GFG {
 
  // Finds if it is possible to partition str
  // into two parts such that first part is
  // divisible by a and second part is divisible
  // by b.
  public static string findDivision(string S, int a,
                                    int b)
  {
    for (int i = 0; i < S.Length - 1; i++) {
 
      string firstPart = S.Substring(0, i + 1);
      string secondPart = S.Substring(i + 1);
 
      if (Convert.ToInt32(firstPart) % a == 0
          && Convert.ToInt32(secondPart) % b == 0) {
        return firstPart + " " + secondPart;
      }
    }
    return "-1";
  }
 
  // Driver code
  public static void Main(string[] args)
  {
    string str = "125";
    int a = 12;
    int b = 3;
    string result = findDivision(str, a, b);
 
    if (result.Equals("-1")) {
      Console.WriteLine("NO");
    }
    else {
      Console.WriteLine("YES");
      Console.WriteLine(result);
    }
  }
}
 
// This code is contributed by phasing17

Javascript

<script>
 
// JavaScript program to check if a string can be splitted
// into two strings such that one is divisible by 'a'
// and other is divisible by 'b'.
 
// Finds if it is possible to partition str
// into two parts such that first part is
// divisible by a and second part is divisible
// by b.
function findDivision(S, a, b){
 
    for(let i=0;i<S.length-1;i++){
 
        let firstPart = S.substring(0,i + 1)
        let secondPart = S.substring(i + 1)
 
        if (parseInt(firstPart) % a == 0
            && parseInt(secondPart) % b == 0)
            return firstPart + " " + secondPart
  }
 
  return "-1"
}
 
// Driver code
let Str = "125"
let a = 12,b = 3
let result = findDivision(Str, a, b)
 
if (result == "-1")
    document.write("NO","</br>")
 
else{
    document.write("YES","</br>")
    document.write(result,"</br>")
}
 
// This code is contributed by shinjanpatra
 
</script>
Producción

NO

Complejidad de tiempo: O(n) donde n es la longitud de la string de números de entrada.
Espacio Auxiliar: O(1)

Este artículo es una contribución de Ekta Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Otro enfoque: (sin usar la función incorporada) 

Complejidad de tiempo: O(n) donde n es la longitud de la string de números de entrada.
Espacio Auxiliar: O(1)

C++

#include <bits/stdc++.h>
using namespace std;
// This code kind of uses sliding window technique. First
// checking if string[0] and string[0..n-1] is divisible if
// yes then return else run a loop from 1 to n-1 and check if
// taking this (0-i)index number and (i+1 to n-1)index number
// on our two declared variables if they are divisible by given two numbers respectively
// in any iteration return them simply
string stringPartition(string s, int a, int b)
{
    // code here
    int n = s.length();
  // if length is 1 not posible
    if (n == 1) {
        return "-1";
    }
    else {
      // Checking if number formed bt S[0] and S[1->n-1] is divisible
        int a1 = s[0] - '0';
        int a2 = s[1] - '0';
        int multiplyer = 10;
        for (int i = 2; i < n; i++) {
            a2 = a2 * multiplyer + (s[i] - '0');
        }
        int i = 1;
        if (a1 % a == 0 && a2 % b == 0) {
            string k1 = string(1, s[0]);
            string k2 = "";
            for (int j = 1; j < n; j++)
                k2 += s[j];
            return k1 + " " + k2; // return the numbers formed as string
        }
      // from here by using sliding window technique we will iterate and check for every i
      // that if the two current numbers formed are divisble if yes return
      // else form the two new numbers for next iteration using sliding window technique
        int q1 = 10;
        int q2 = 1;
        for (int i = 1; i < n - 1; i++)
            q2 *= 10;
        while (i < n - 1) {
            char x = s[i];
            int ad = x - '0';
            a1 = a1 * q1 + ad;
            a2 = a2 - q2 * ad;
            if (a1 % a == 0 && a2 % b == 0) {
                string k1 = "";
                string k2 = "";
                for (int j = 0; j < i + 1; j++)
                    k1 += s[j];
                for (int j = i + 1; j < n; j++)
                    k2 += s[j];
                return k1 + " " + k2;
            }
            q2 /= 10;
            i++;
        }
    }
    return "-1";
}
// Driver code
int main()
{
    string str = "123";
    int a = 12, b = 3;
    string result = stringPartition(str, a, b);
 
    if (result == "-1") {
        cout << "NO" << endl;
    }
    else {
        cout << "YES" << endl;
        cout << result << endl;
    }
 
    return 0;
}
// This code is contributed by Kartikey Singh
Producción

YES
12 3

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *