Dado un número grande en formato de string, también se nos dan dos números f y s. Necesitamos dividir el número grande en dos partes continuas de modo que la primera parte sea divisible por f y la segunda parte sea divisible por s.
Ejemplos:
Input: num = “246904096”
f = 12345
s = 1024
Output: Yes
We can divide num into “24680” and “4096”
which are divisible by f and s respectively.
Input : num = “1234”
f = 1
s = 123
Output : No
We can not divide num into two parts under
given constraint.
Una solución simple es generar todas las divisiones de un número dado y verificar si una división es divisible.
Podemos resolver este problema almacenando los restos de cada prefijo y sufijo de la string dada y si en cualquier índice, recordatorio de prefijo y recordatorio de sufijo ambos son cero, entonces sabemos que podemos romper la string en este índice. El procedimiento se explica para el ejemplo anterior,
String = “246904096” All prefix reminders with 12345 are, Prefix 2 reminder with 12345, 2 prefix 24 reminder with 12345, 24 prefix 246 reminder with 12345, 246 prefix 2469 reminder with 12345, 2469 prefix 24690 reminder with 12345, 0 prefix 246904 reminder with 12345, 4 prefix 2469040 reminder with 12345, 40 prefix 24690409 reminder with 12345, 409 prefix 246904096 reminder with 12345, 4096 All suffix reminder with 1024 are, Suffix 6 reminder with 1024, 6 Suffix 96 reminder with 1024, 96 Suffix 096 reminder with 1024, 96 Suffix 4096 reminder with 1024, 0 Suffix 04096 reminder with 1024, 0 Suffix 904096 reminder with 1024, 928 Suffix 6904096 reminder with 1024, 288 Suffix 46904096 reminder with 1024, 800 Suffix 246904096 reminder with 1024, 288 Now we can see that at index 5 both reminders are 0, so the string can be broken into 24680 and 4096.
Podemos obtener (i)th recordatorio de sufijo por (i – 1)th recordatorio de sufijo como, (sr[i] = sr[i – 1] * 10 + s[i]) % f, es decir, simplemente multiplique el recordatorio anterior por 10 y agregue el dígito actual y luego tome un recordatorio por f.
Para obtener (i)th prefijo recordatorio por (i + 1)th prefijo recordatorio, podemos hacer, (pr[i] = pr[i + 1] + s[i] * base) % s, es decir, agregar el siguiente recordatorio y dígito actual multiplicado por el valor base que será 1 para el último dígito, 10 para el penúltimo dígito y así sucesivamente y luego tomaremos un recordatorio por s en general.
La complejidad temporal total de la solución será O(N)
C++
// C++ code to break the number string into
// two divisible parts by given numbers
#include <bits/stdc++.h>
using namespace std;
// method prints divisible parts if possible,
// otherwise prints 'Not possible'
void printTwoDivisibleParts(string num, int f, int s)
{
int N = num.length();
// creating arrays to store reminder
int prefixReminder[N + 1];
int suffixReminder[N + 1];
suffixReminder[0] = 0;
// looping over all suffix and storing
// reminder with f
for (int i = 1; i < N; i++)
// getting suffix reminder from previous
// suffix reminder
suffixReminder[i] = (suffixReminder[i - 1] * 10 +
(num[i - 1] - '0')) % f;
prefixReminder[N] = 0;
int base = 1;
// looping over all prefix and storing
// reminder with s
for (int i = N - 1; i >= 0; i--) {
// getting prefix reminder from next
// prefix reminder
prefixReminder[i] = (prefixReminder[i + 1] +
(num[i] - '0') * base) % s;
// updating base value
base = (base * 10) % s;
}
// now looping over all reminders to check
// partition condition
for (int i = 0; i < N; i++) {
// if both reminders are 0 and digit itself
// is not 0, then print result and return
if (prefixReminder[i] == 0 &&
suffixReminder[i] == 0 &&
num[i] != '0') {
cout << num.substr(0, i) << " "
<< num.substr(i) << endl;
return;
}
}
// if we reach here, then string can' be
// partitioned under constraints
cout << "Not Possible\n";
}
// Driver code to test above methods
int main()
{
string num = "246904096";
int f = 12345;
int s = 1024;
printTwoDivisibleParts(num, f, s);
return 0;
}
Java
// Java program to break the number string
// into two divisible parts by given numbers
public class DivisibleParts
{
// method prints divisible parts if
// possible, otherwise prints 'Not possible'
static void printTwoDivisibleParts(String num,
int f, int s)
{
int N = num.length();
// creating arrays to store reminder
int[] prefixReminder = new int[N + 1];
int[] suffixReminder = new int[N + 1];
suffixReminder[0] = 0;
// looping over all suffix and storing
// reminder with f
for (int i = 1; i < N; i++)
// getting suffix reminder from
// previous suffix reminder
suffixReminder[i] = (suffixReminder[i - 1] * 10 +
(num.charAt(i - 1) - '0')) % f;
prefixReminder[N] = 0;
int base = 1;
// looping over all prefix and storing
// reminder with s
for (int i = N - 1; i >= 0; i--) {
// getting prefix reminder from next
// prefix reminder
prefixReminder[i] = (prefixReminder[i + 1] +
(num.charAt(i ) - '0') * base) % s;
// updating base value
base = (base * 10) % s;
}
// now looping over all reminders to
// check partition condition
for (int i = 0; i < N; i++) {
// if both reminders are 0 and digit
// itself is not 0, then print result
// and return
if (prefixReminder[i] == 0 &&
suffixReminder[i] == 0 &&
num.charAt(i ) != '0') {
System.out.println( num.substring(0, i)
+" " + num.substring(i));
return;
}
}
// if we reach here, then string can' be
// partitioned under constraints
System.out.println("Not Possible");
}
/* Driver program */
public static void main(String[] args)
{
String num = "246904096";
int f = 12345;
int s = 1024;
printTwoDivisibleParts(num, f, s);
}
}
// This code is contributed by Prerna Saini
Python3
# Python3 code to break the
# number string into two
# divisible parts by given
# numbers
# method prints divisible
# parts if possible, otherwise
# prints 'Not possible'
def printTwoDivisibleParts(num, f, s):
N = len(num);
# creating arrays
# to store reminder
prefixReminder = [0]*(N + 1);
suffixReminder = [0]*(N + 1);
# looping over all
# suffix and storing
# reminder with f
for i in range(1,N):
# getting suffix
# reminder from previous
# suffix reminder
suffixReminder[i] = (suffixReminder[i - 1] * 10 +
(ord(num[i - 1]) -
48)) % f;
base = 1;
# looping over all
# prefix and storing
# reminder with s
for i in range(N - 1,-1,-1):
# getting prefix
# reminder from next
# prefix reminder
prefixReminder[i] = (prefixReminder[i + 1] +
(ord(num[i]) - 48) *
base) % s;
# updating base value
base = (base * 10) % s;
# now looping over
# all reminders to check
# partition condition
for i in range(N):
# if both reminders are
# 0 and digit itself
# is not 0, then print
# result and return
if (prefixReminder[i] == 0 and suffixReminder[i] == 0 and num[i] != '0'):
print(num[0:i],num[i:N]);
return 0;
# if we reach here, then
# string can' be partitioned
# under constraints
print("Not Possible");
# Driver code
if __name__=='__main__':
num = "246904096";
f = 12345;
s = 1024;
printTwoDivisibleParts(num,f, s);
# This code is contributed
# by mits
C#
// C# program to break the
// number string into two
// divisible parts by given
// numbers
using System;
class GFG
{
// method prints divisible
// parts if possible, otherwise
// prints 'Not possible'
static void printTwoDivisibleParts(String num,
int f, int s)
{
int N = num.Length;
// creating arrays to
// store reminder
int[] prefixReminder = new int[N + 1];
int[] suffixReminder = new int[N + 1];
suffixReminder[0] = 0;
// looping over all
// suffix and storing
// reminder with f
for (int i = 1; i < N; i++)
// getting suffix reminder from
// previous suffix reminder
suffixReminder[i] = (suffixReminder[i - 1] * 10 +
(num[i - 1] - '0')) % f;
prefixReminder[N] = 0;
int base1 = 1;
// looping over all
// prefix and storing
// reminder with s
for (int i = N - 1; i >= 0; i--)
{
// getting prefix reminder
// from next prefix reminder
prefixReminder[i] = (prefixReminder[i + 1] +
(num[i] - '0') * base1) % s;
// updating base1 value
base1 = (base1 * 10) % s;
}
// now looping over all
// reminders to check
// partition condition
for (int i = 0; i < N; i++)
{
// if both reminders are
// 0 and digit itself is
// not 0, then print result
// and return
if (prefixReminder[i] == 0 &&
suffixReminder[i] == 0 &&
num[i] != '0')
{
Console.WriteLine(num.Substring(0, i) +
" " + num.Substring(i));
return;
}
}
// if we reach here, then
// string can' be partitioned
// under constraints
Console.WriteLine("Not Possible");
}
// Driver Code
public static void Main()
{
String num = "246904096";
int f = 12345;
int s = 1024;
printTwoDivisibleParts(num, f, s);
}
}
// This code is contributed by mits
PHP
<?php
// PHP code to break the
// number string into two
// divisible parts by given
// numbers
// method prints divisible
// parts if possible, otherwise
// prints 'Not possible'
function printTwoDivisibleParts($num, $f, $s)
{
$N = strlen($num);
// creating arrays
// to store reminder
$prefixReminder = array_fill(0, $N + 1, 0);
$suffixReminder = array_fill(0, $N + 1, 0);
// looping over all
// suffix and storing
// reminder with f
for ($i = 1; $i < $N; $i++)
// getting suffix
// reminder from previous
// suffix reminder
$suffixReminder[$i] = ($suffixReminder[$i - 1] * 10 +
(ord($num[$i - 1]) -
48)) % $f;
$base = 1;
// looping over all
// prefix and storing
// reminder with s
for ($i = $N - 1; $i >= 0; $i--)
{
// getting prefix
// reminder from next
// prefix reminder
$prefixReminder[$i] = ($prefixReminder[$i + 1] +
(ord($num[$i]) - 48) *
$base) % $s;
// updating base value
$base = ($base * 10) % $s;
}
// now looping over
// all reminders to check
// partition condition
for ($i = 0; $i < $N; $i++)
{
// if both reminders are
// 0 and digit itself
// is not 0, then print
// result and return
if ($prefixReminder[$i] == 0 &&
$suffixReminder[$i] == 0 &&
$num[$i] != '0')
{
echo substr($num, 0, $i)." ".
substr($num,$i)."\n";
return;
}
}
// if we reach here, then
// string can' be partitioned
// under constraints
echo "Not Possible\n";
}
// Driver code
$num = "246904096";
$f = 12345;
$s = 1024;
printTwoDivisibleParts($num,
$f, $s);
// This code is contributed
// by mits
?>
Javascript
<script>
// javascript program to break the
// number string into two
// divisible parts by given
// numbers
// method prints divisible
// parts if possible, otherwise
// prints 'Not possible'
function printTwoDivisibleParts( num, f, s)
{
var N = num.length;
// creating arrays to
// store reminder
var prefixReminder = []
var suffixReminder = []
suffixReminder[0] = 0;
// looping over all
// suffix and storing
// reminder with f
for (var i = 1; i < N; i++)
// getting suffix reminder from
// previous suffix reminder
suffixReminder[i] = (suffixReminder[i - 1] * 10 + (num[i - 1] - '0')) % f;
prefixReminder[N] = 0;
var base1 = 1;
// looping over all
// prefix and storing
// reminder with s
for (var i = N - 1; i >= 0; i--)
{
// getting prefix reminder
// from next prefix reminder
prefixReminder[i] = (prefixReminder[i + 1] + (num[i] - '0') * base1) % s;
// updating base1 value
base1 = (base1 * 10) % s;
}
// now looping over all
// reminders to check
// partition condition
for (var i = 0; i < N; i++)
{
// if both reminders are
// 0 and digit itself is
// not 0, then print result
// and return
if (prefixReminder[i] == 0 && suffixReminder[i] == 0 && num[i] != '0')
{
document.write(num.substring(0, i) + " " + num.substring(i));
return;
}
}
// if we reach here, then
// string can' be partitioned
// under constraints
document.write("Not Possible");
}
// Driver Code
var num = "246904096";
var f = 12345;
var s = 1024;
printTwoDivisibleParts(num, f, s);
// This code is contributed by bunnyram19.
</script>
Producción:
24690 4096
Complejidad de tiempo: O(N)
Espacio auxiliar: O(N)
Este artículo es una contribución de Utkarsh Trivedi . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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