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: SÍ
12 00Entrada: 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