Dado un número N muy grande, necesitamos contar las formas totales de manera que si dividimos el número en dos partes a y b , la primera parte a puede obtenerse mediante la división integral de la segunda b por alguna potencia p de 10 y p> =0. 1 <= No de dígitos en N <= 
.
Ejemplos:
Input : 220 Output : 1 220 can be divided as a = 2 and b = 20 such that for p = 1, b/10 = a. Input : 1111 Output : 2 We get answer 2 because we need to consider integral division. Let's consider the first partition a = 1, b = 111. for p = 2, b/pow(10,p) = a thus this is a valid partition. now a = 11, b = 11. for p = 0, b/pow(10,p) = a thus this too is a valid combination. Input : 2202200 Output : 2 for a = 2 b = 202200, p = 5 and a = 220, b = 2200, p = 1
Dado que el número puede ser muy grande para estar contenido incluso en un int largo, lo almacenaremos como una string. Según las condiciones mencionadas en el problema, la división es la función suelo. Un enfoque simple e ineficiente será dividir la string en dos substrings y luego convertirlas en enteros y realizar la división. Un método eficiente para hacerlo será usar la función de comparación de strings para hacer coincidir los dígitos más significativos de las dos strings e ignorar el resto (función de piso).
A continuación se muestra la implementación de esta idea:
C++
#include <bits/stdc++.h>
using namespace std;
// c++ function to count ways to divide a
// string in two parts a and b such that
// b/pow(10, p) == a
int calculate(string N)
{
int len = N.length();
int l = (len) / 2;
int count = 0;
for (int i = 1; i <= l; i++) {
// substring representing int a
string s = N.substr(0, i);
// no of digits in a
int l1 = s.length();
// consider only most significant
// l1 characters of remaining string
// for int b
string t = N.substr(i, l1);
// if any of a or b contains leading 0s
// discard this combination
if (s[0] == '0' || t[0] == '0')
continue;
// if both are equal
if (s.compare(t) == 0)
count++;
}
return count;
}
// driver function to test above function
int main()
{
string N = "2202200";
cout << calculate(N);
return 0;
}
Java
// Java program to count ways to divide a
// String in two parts a and b such that
// b/pow(10, p) == a
import java.util.*;
class GFG
{
static int calculate(String N)
{
int len = N.length();
int l = (len) / 2;
int count = 0;
for (int i = 1; i <= l; i++)
{
// subString representing int a
String s = N.substring(0, i);
// no of digits in a
int l1 = s.length();
// consider only most significant
// l1 characters of remaining String
// for int b
String t = N.substring(i, l1 + i);
// if any of a or b contains leading 0s
// discard this combination
if (s.charAt(0) == '0' || t.charAt(0) == '0')
continue;
// if both are equal
if (s.compareTo(t) == 0)
count++;
}
return count;
}
// Driver Code
public static void main(String[] args)
{
String N = "2202200";
System.out.print(calculate(N));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to count ways to divide
# a string in two parts a and b such that
# b/pow(10, p) == a
def calculate( N ):
length = len(N)
l = int((length) / 2)
count = 0
for i in range(l + 1):
print(i)
# substring representing int a
s = N[0: 0 + i]
# no of digits in a
l1 = len(s)
print(s,l1)
# consider only most significant
# l1 characters of remaining
# string for int b
t = N[i: l1 + i]
# if any of a or b contains
# leading 0s discard this
try:
if s[0] == '0' or t[0] == '0':
continue
except:
continue
# if both are equal
if s == t:
count+=1
print(i,N[i],count)
return count
# driver code to test above function
N = str("2202200")
print(calculate(N))
# This code is contributed by "Sharad_Bhardwaj".
C#
// C# program to count ways to divide a
// String in two parts a and b such that
// b/pow(10, p) == a
using System;
class GFG
{
static int calculate(String N)
{
int len = N.Length;
int l = (len) / 2;
int count = 0;
for (int i = 1; i <= l; i++)
{
// subString representing int a
String s = N.Substring(0, i);
// no of digits in a
int l1 = s.Length;
// consider only most significant
// l1 characters of remaining String
// for int b
String t = N.Substring(i, l1);
// if any of a or b contains leading 0s
// discard this combination
if (s[0] == '0' || t[0] == '0')
continue;
// if both are equal
if (s.CompareTo(t) == 0)
count++;
}
return count;
}
// Driver Code
public static void Main(String[] args)
{
String N = "2202200";
Console.Write(calculate(N));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to count ways to divide
// a string in two parts a and b such that
// b/pow(10, p) == a
function calculate( N ){
let len = N.length
let l = Math.floor((len) / 2)
let count = 0
for(let i = 1; i < l + 1; i++)
{
// substring representing int a
let s = N.substr(0, i)
// no of digits in a
let l1 = s.length
// consider only most significant
// l1 characters of remaining
// string for int b
let t = N.substr(i,l1)
// if any of a or b contains
// leading 0s discard this
if (s[0] == '0' || t[0] == '0'){
continue
}
// if both are equal
if(s === t)
count++
}
return count
}
// driver code to test above function
let N = "2202200"
console.log(calculate(N))
// This code is contributed by shinjanpatra
</script>
Producción
2
Complejidad de Tiempo: O(n 2 )
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por aditi sharma 2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA