Dado un entero D , la tarea es encontrar el conteo de todos los posibles enteros positivos N tales que reverse(N) = N + D .
Ejemplos:
Entrada: D = 63
Salida: 2
Explicación:
Para N = 18, 18 + 63 = 81, lo que satisface la condición N + D = inversa(N).
Para N = 29, 29 + 63 = 92, lo que satisface la condición N + D = inversa(N).
Por lo tanto, la salida requerida es 2Entrada: D = 75
Salida: 0
Enfoque: El problema se puede resolver con base en las siguientes observaciones:
N + D = inversa(N) => N – inversa(N) = D
=> D = ∑ (i=0 a [L/2]-1) (10 L-1-i -10 i )*( n i – n L-1-i ), L = Conteo de dígitos en N.Si re yo = norte yo − norte L−1−i (0 ≤ yo ≤ ⌊L/2⌋ − 1) inversa(N) − N = ∑ ( i =0 a [L/2]-1) (10 L -1-i -10 i )*d i
Siga los pasos a continuación para resolver el problema:
- Sea f(L, D) = inversa(N) − N . Encontrar el número de N que satisface la fórmula dada es casi equivalente a enumerar los pares de L y una secuencia de números enteros en el rango [−9, 9] , { d 0 , d 1 , . . ., d ⌊L/2⌋−1 } (tenga en cuenta que hay más de un N que corresponde a una secuencia de d i ). Aquí, para cualquier i tal que 0 ≤ i < ⌊L/2⌋ − 1 , se cumple lo siguiente:
10 L−1−i − 10 i > ∑ (j=i+1 a [L/2 – 1]) ((10 L−1−j − 10 j ) · 9) + 10 L−⌊L/2⌋
- Sea L D el número de dígitos de D en notación decimal. Entonces, cuando L > 2L D y f(L, d) > 0 , se puede ver que f(L, d) > D .
- Por lo tanto, es suficiente considerar los valores entre L D y 2L D como el valor de L .
- Para un valor fijo de L , considere enumerar las sucesiones { d 0 , d 1 , …, d ⌊L/2⌋−1 } tales que f(L, d) = D (y encontrar el conteo de N que satisfaga el fórmula), realizando la primera búsqueda en profundidad a partir de d 0 .
- Cuando los valores hasta d i−1 ya están decididos, se puede ver que como máximo hay dos candidatos del valor de d i que hay que considerar: el valor máximo tal que (10 i − 10 L−1− i )d i ≤ dif , y el valor mínimo tal que (10 i − 10 L−1−i )d i > dif . (Intuitivamente, si el valor “medio” de f(L, d) durante la búsqueda se aleja demasiado de D , no es posible “regresar” y, por lo tanto, debe “permanecer cerca” de D ).
- Por lo tanto, para un valor fijo de L , encuentre el conteo de N que satisface la fórmula dada en O(2 ⌊L/2⌋ ) tiempo.
A continuación se muestra la implementación del enfoque anterior:
C++
// Cpp program for the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Maximum digits in N
int MAXL = 17;
int N;
vector<int> v;
// Function to find count
// of possible values
// of N such that N + D = reverse(N)
int count(int D, int l, int t, int x[])
{
// Base Case
if (t == N) {
// If D is not equal to 0
if (D != 0)
return 0;
// Stores count of possible values
// of N such that N + D = reverse(N)
long ans = 1;
for (int i = 0; i < N; i++) {
// Update ans
ans *= (i == 0 ? 9 : 10) - abs(x[i]);
}
// If l is even
if (l % 2 == 0) {
// Update ans
ans *= 10;
}
return ans;
}
// Stores count of possible values
// of N such that N + D = reverse(N)
long ans = 0;
// Iterate over the range [-9, 9]
for (int m = -9; m <= 9; m++) {
if (-v[t] < D + v[t] * m && D +
v[t] * m < v[t]) {
x[t] = m;
// Update ans
ans += count(D + v[t] * m, l,
t + 1, x);
}
}
return ans;
}
// Utility function to find count of N
// such that N + D = reverse(N)
int findN(int D)
{
// If d is a multiple of 9,
// no such value N found
if (D % 9 != 0)
return 0;
// Divide D by 9 check reverse
// of number and its sum
D /= 9;
// B[i]: Stores power of (10, i)
vector<int> B(MAXL);
B[0] = 1;
// Calculate power(10, i)
for (int i = 1; i < MAXL; i++) {
// Update B[i]
B[i] = B[i - 1] * 10;
}
// Stores count of N such
// that N + D = reverse(N)
int ans = 0;
// Iterate over the range [1, MAXL]
for (int i = 1; i <= MAXL; i++) {
N = (i + 1) / 2;
v.clear();
v.resize(N);
for (int j = 0; j < N; j++)
for (int k = j; k < i - j; k++)
v[j] += B[k];
int arr[N];
ans += count(D, i, 0, arr);
}
return ans;
}
// Driver Code
int main()
{
int D = 63;
// Function call
cout << findN(D);
}
Java
// Java program of the above approach
import java.util.*;
public class Main {
// Maximum digits in N
static final int MAXL = 17;
static int N;
static long[] v;
// Utility function to find count of N
// such that N + D = reverse(N)
static long findN(int D)
{
// If d is a multiple of 9,
// no such value N found
if (D % 9 != 0)
return 0;
// Divide D by 9 check reverse
// of number and its sum
D /= 9;
// B[i]: Stores power of (10, i)
long[] B = new long[MAXL];
B[0] = 1;
// Calculate power(10, i)
for (int i = 1; i < MAXL; i++) {
// Update B[i]
B[i] = B[i - 1] * 10;
}
// Stores count of N such
// that N + D = reverse(N)
long ans = 0;
// Iterate over the range [1, MAXL]
for (int i = 1; i <= MAXL; i++) {
N = (i + 1) / 2;
v = new long[N];
for (int j = 0; j < N; j++)
for (int k = j; k < i - j; k++)
v[j] += B[k];
// Update ans
ans += count(D, i, 0, new int[N]);
}
return ans;
}
// Function to find count of possible values
// of N such that N + D = reverse(N)
static long count(long D, int l,
int t, int[] x)
{
// Base Case
if (t == N) {
// If D is not equal to 0
if (D != 0)
return 0;
// Stores count of possible values
// of N such that N + D = reverse(N)
long ans = 1;
for (int i = 0; i < N; i++) {
// Update ans
ans *= (i == 0 ? 9 : 10)
- Math.abs(x[i]);
}
// If l is even
if (l % 2 == 0) {
// Update ans
ans *= 10;
}
return ans;
}
// Stores count of possible values
// of N such that N + D = reverse(N)
long ans = 0;
// Iterate over the range [-9, 9]
for (int m = -9; m <= 9; m++) {
if (-v[t] < D + v[t] * m
&& D + v[t] * m < v[t]) {
x[t] = m;
// Update ans
ans += count(D + v[t] * m,
l, t + 1, x);
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int D = 63;
// Function call
System.out.println(findN(D));
sc.close();
}
}
Python3
# Python program of the above approach # Maximum digits in N MAXL = 17; N = 0; v = 0; # Utility function to find count of N # such that N + D = reverse(N) def findN(D): global N; global v; # If d is a multiple of 9, # no such value N found if (D % 9 != 0): return 0; # Divide D by 9 check reverse # of number and its sum D //= 9; # B[i]: Stores power of (10, i) B = [0]*MAXL; B[0] = 1; # Calculate power(10, i) for i in range(1, MAXL): # Update B[i] B[i] = B[i - 1] * 10; # Stores count of N such # that N + D = reverse(N) ans = 0; # Iterate over the range [1, MAXL] for i in range(1, MAXL + 1): N = (i + 1) // 2; v = [0]*N; for j in range(N): for k in range(j, i - j): v[j] += B[k]; # Update ans temp = [0]*N; ans += count(D, i, 0, temp); return ans; # Function to find count of possible values # of N such that N + D = reverse(N) def count(D, l, t, x): global N; global v; # Base Case if (t == N): # If D is not equal to 0 if (D != 0): return 0; # Stores count of possible values # of N such that N + D = reverse(N) ans = 1; for i in range(N): # Update ans ans *= (9 if i == 0 else 10) - abs(x[i]); # If l is even if (l % 2 == 0): # Update ans ans *= 10; return ans; # Stores count of possible values # of N such that N + D = reverse(N) ans = 0; # Iterate over the range [-9, 9] for m in range(-9, 10): if (-v[t] < D + v[t] * m and D + v[t] * m < v[t]): x[t] = m; # Update ans ans += count(D + v[t] * m, l, t + 1, x); return ans; # Driver Code if __name__ == '__main__': D = 63; # Function call print(findN(D)); # This code is contributed by 29AjayKumar
C#
// C# program for the above approach
using System;
class GFG
{
// Maximum digits in N
static int MAXL = 17;
static int N;
static long[] v;
// Utility function to find count of N
// such that N + D = reverse(N)
static long findN(int D)
{
// If d is a multiple of 9,
// no such value N found
if (D % 9 != 0)
return 0;
// Divide D by 9 check reverse
// of number and its sum
D /= 9;
// B[i]: Stores power of (10, i)
long[] B = new long[MAXL];
B[0] = 1;
// Calculate power(10, i)
for (int i = 1; i < MAXL; i++)
{
// Update B[i]
B[i] = B[i - 1] * 10;
}
// Stores count of N such
// that N + D = reverse(N)
long ans = 0;
// Iterate over the range [1, MAXL]
for (int i = 1; i <= MAXL; i++)
{
N = (i + 1) / 2;
v = new long[N];
for (int j = 0; j < N; j++)
for (int k = j; k < i - j; k++)
v[j] += B[k];
// Update ans
ans += count(D, i, 0, new int[N]);
}
return ans;
}
// Function to find count of possible values
// of N such that N + D = reverse(N)
static long count(long D, int l,
int t, int[] x)
{
// Base Case
if (t == N)
{
// If D is not equal to 0
if (D != 0)
return 0;
// Stores count of possible values
// of N such that N + D = reverse(N)
long ans = 1;
for (int i = 0; i < N; i++)
{
// Update ans
ans *= (i == 0 ? 9 : 10)
- Math.Abs(x[i]);
}
// If l is even
if (l % 2 == 0)
{
// Update ans
ans *= 10;
}
return ans;
}
// Stores count of possible values
// of N such that N + D = reverse(N)
long anss = 0;
// Iterate over the range [-9, 9]
for (int m = -9; m <= 9; m++)
{
if (-v[t] < D + v[t] * m
&& D + v[t] * m < v[t])
{
x[t] = m;
// Update ans
anss += count(D + v[t] * m,
l, t + 1, x);
}
}
return anss;
}
// Driver code
public static void Main(String[] args)
{
int D = 63;
// Function call
Console.WriteLine(findN(D));
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// javascript program of the above approach
// Maximum digits in N
let MAXL = 17;
let N;
let v = []
// Utility function to find count of N
// such that N + D = reverse(N)
function findN(D)
{
// If d is a multiple of 9,
// no such value N found
if (D % 9 != 0)
return 0;
// Divide D by 9 check reverse
// of number and its sum
D /= 9;
// B[i]: Stores power of (10, i)
let B = new Array(MAXL).fill(0);
B[0] = 1;
// Calculate power(10, i)
for (let i = 1; i < MAXL; i++) {
// Update B[i]
B[i] = B[i - 1] * 10;
}
// Stores count of N such
// that N + D = reverse(N)
let ans = 0;
// Iterate over the range [1, MAXL]
for (let i = 1; i <= MAXL; i++) {
N = Math.floor((i + 1) / 2);
v = new Array(N).fill(0);
for (let j = 0; j < N; j++)
for (let k = j; k < i - j; k++)
v[j] += B[k];
// Update ans
ans += count(D, i, 0, new Array(N));
}
return ans;
}
// Function to find count of possible values
// of N such that N + D = reverse(N)
function count(D, l, t, x)
{
// Base Case
if (t == N) {
// If D is not equal to 0
if (D != 0)
return 0;
// Stores count of possible values
// of N such that N + D = reverse(N)
let ans = 1;
for (let i = 0; i < N; i++) {
// Update ans
ans *= (i == 0 ? 9 : 10)
- Math.abs(x[i]);
}
// If l is even
if (l % 2 == 0) {
// Update ans
ans *= 10;
}
return ans;
}
// Stores count of possible values
// of N such that N + D = reverse(N)
let ans = 0;
// Iterate over the range [-9, 9]
for (let m = -9; m <= 9; m++)
{
if (-v[t] < D + v[t] * m
&& D + v[t] * m < v[t])
{
x[t] = m;
// Update ans
ans += count(D + v[t] * m,
l, t + 1, x);
}
}
return ans;
}
// Driver Code
let D = 63;
// Function call
document.write(findN(D));
// This code is contributed by target_2.
</script>
Producción:
2
Complejidad de tiempo: O(2 L D ), donde L D denota el número de dígitos de D en notación decimal.
Espacio Auxiliar: O( L D )
Publicación traducida automáticamente
Artículo escrito por huzaifa0602 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA