Dados dos números X e Y de la misma longitud, la tarea es encontrar el número mínimo d que debe agregarse a todos los dígitos de X para que sea mayor que Y.
Ejemplos:
Entrada: X = 123, Y = 222
Salida: 1
Explicación:
Agregue 1 a todos los dígitos de X
Entonces X se convierte en {2, 3, 4} que es
lexicográficamente más grande que {2, 2, 2}.
Entrada: X = 4512, Y = 2998
Salida: 0
Explicación:
X ya es lexicográficamente más grande que Y
, por lo que la respuesta será 0.
Enfoque: este problema se puede resolver fácilmente dividiéndolo en tres casos
- Caso 1: encuentre si X ya es lexicográficamente más grande que Y. Si es así, entonces no necesitamos hacer nada.
- Caso 2: De lo contrario, agregue (Y[0] – X[0]) a todos los elementos de X y luego verifique si X es lexicográficamente más grande que Y o no.
- Caso 3: si aún no es más grande, entonces la respuesta será (Y[0] – X[0]) + 1 porque los primeros elementos de X se vuelven más grandes que el primer elemento de Y significa que X[0] > Y[0] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find Minimum number to be added
// to all digits of X to make X > Y
#include <bits/stdc++.h>
using namespace std;
// Function to check if X
// is lexicographically larger Y
bool IsLarger(int X[], int Y[], int n)
{
for (int i = 0; i < n; i++) {
// It is lexicographically larger
if (X[i] < Y[i]) {
return false;
}
}
return true;
}
// Utility function to check
// minimum value of d
int solve(int X[], int Y[], int n)
{
int ans = 0;
// If X is already larger
// do not need to add anything
if (IsLarger(X, Y, n)) {
ans = 0;
}
else {
// Adding d to all elements of X
int d = Y[0] - X[0];
for (int i = 0; i < n; i++) {
X[i] += d;
}
// If X is larger now
// print d
if (IsLarger(X, Y, n)) {
ans = d;
}
// else print d + 1
else {
ans = d + 1;
}
}
return ans;
}
// Driver Code
int main()
{
// Taking the numbers as sequences
int X[] = { 2, 3, 6, 9 };
int Y[] = { 3, 4, 8, 1 };
int n = sizeof(X) / sizeof(X[0]);
cout << solve(X, Y, n);
return 0;
}
Java
// Java program to find Minimum number to be added
// to all digits of X to make X > Y
import java.util.*;
class GFG
{
// Function to check if X
// is lexicographically larger Y
static boolean IsLarger(int[] X,
int[] Y, int n)
{
for (int i = 0; i < n; i++)
{
// It is lexicographically larger
if (X[i] < Y[i])
{
return false;
}
}
return true;
}
// Utility function to check
// minimum value of d
static int solve(int X[], int Y[], int n)
{
int ans = 0;
// If X is already larger
// do not need to add anything
if (IsLarger(X, Y, n))
ans = 0;
else
{
// Adding d to all elements of X
int d = Y[0] - X[0];
for (int i = 0; i < n; i++)
X[i] += d;
// If X is larger now
// print d
if (IsLarger(X, Y, n))
ans = d;
// else print d + 1
else
{
ans = d + 1;
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Taking the numbers as sequences
int X[] = { 2, 3, 6, 9 };
int Y[] = { 3, 4, 8, 1 };
int n = X.length;
System.out.println(solve(X, Y, n));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to find Minimum number to be added # to all digits of X to make X > Y # Function to check if X # is lexicographically larger Y def IsLarger(X, Y, n) : for i in range(n) : # It is lexicographically larger if (X[i] < Y[i]) : return False; return True; # Utility function to check # minimum value of d def solve(X, Y, n) : ans = 0; # If X is already larger # do not need to add anything if (IsLarger(X, Y, n)) : ans = 0; else : # Adding d to all elements of X d = Y[0] - X[0]; for i in range(n) : X[i] += d; # If X is larger now # print d if (IsLarger(X, Y, n)) : ans = d; # else print d + 1 else : ans = d + 1; return ans; # Driver Code if __name__ == "__main__" : # Taking the numbers as sequences X = [ 2, 3, 6, 9 ]; Y = [ 3, 4, 8, 1 ]; n = len(X); print(solve(X, Y, n)); # This code is contributed by AnkitRai01
C#
// C# program to find Minimum number to be.Added
// to all digits of X to make X > Y
using System;
class GFG
{
// Function to check if X
// is lexicographically larger Y
static bool IsLarger(int[] X,
int[] Y, int n)
{
for (int i = 0; i < n; i++)
{
// It is lexicographically larger
if (X[i] < Y[i])
{
return false;
}
}
return true;
}
// Utility function to check
// minimum value of d
static int solve(int []X, int []Y, int n)
{
int ans = 0;
// If X is already larger
// do not need to.Add anything
if (IsLarger(X, Y, n))
ans = 0;
else
{
// Adding d to all elements of X
int d = Y[0] - X[0];
for (int i = 0; i < n; i++)
X[i] += d;
// If X is larger now
// print d
if (IsLarger(X, Y, n))
ans = d;
// else print d + 1
else
{
ans = d + 1;
}
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
// Taking the numbers as sequences
int []X = { 2, 3, 6, 9 };
int []Y = { 3, 4, 8, 1 };
int n = X.Length;
Console.WriteLine(solve(X, Y, n));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// javascript program to find Minimum number to be added
// to all digits of X to make X > Y
// Function to check if X
// is lexicographically larger Y
function IsLarger(X, Y, n)
{
for (let i = 0; i < n; i++) {
// It is lexicographically larger
if (X[i] < Y[i]) {
return false;
}
}
return true;
}
// Utility function to check
// minimum value of d
function solve(X, Y, n)
{
let ans = 0;
// If X is already larger
// do not need to add anything
if (IsLarger(X, Y, n)) {
ans = 0;
}
else {
// Adding d to all elements of X
let d = Y[0] - X[0];
for (let i = 0; i < n; i++) {
X[i] += d;
}
// If X is larger now
// print d
if (IsLarger(X, Y, n)) {
ans = d;
}
// else print d + 1
else {
ans = d + 1;
}
}
return ans;
}
// Driver Code
// Taking the numbers as sequences
let X = [ 2, 3, 6, 9 ];
let Y = [ 3, 4, 8, 1 ];
let n = X.length;
document.write(solve(X, Y, n));
// This code is contributed by souravmahato348.
</script>
Producción:
2
Complejidad de tiempo: 
, donde N es la longitud de X o Y
Espacio auxiliar: O(1)