Dados tres enteros X , Y y N , la tarea es encontrar el mayor número posible de longitud N que consista solo en X e Y como sus dígitos, de modo que la cuenta de X en él sea divisible por Y y viceversa . Si no se puede formar tal número, imprima -1 .
Ejemplos:
Entrada: N = 3, X = 5, Y = 3
Salida: 555
Explicación:
Cuenta de 5 = 3, que es divisible por 3
Cuenta de 3 = 0
Entrada: N = 4, X = 7, Y = 5
Salida: – 1
Enfoque:
siga los pasos a continuación para resolver el problema:
- Considere el mayor de X e Y como X y el menor como Y .
- Dado que el número debe tener una longitud N , realice los siguientes dos pasos hasta que N ≤ 0:
- Si N es divisible por Y, agregue X, N veces a la respuesta y reduzca N a cero.
- De lo contrario, reduzca N por X y agregue Y, X veces a la respuesta.
- Después de completar el paso anterior, si N <0, entonces no es posible un número del tipo requerido. Imprimir -1 .
- De lo contrario, imprime la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to generate and return
// the largest number
void largestNumber(int n, int X, int Y)
{
int maxm = max(X, Y);
// Store the smaller in Y
Y = X + Y - maxm;
// Store the larger in X
X = maxm;
// Stores respective counts
int Xs = 0;
int Ys = 0;
while (n > 0) {
// If N is divisible by Y
if (n % Y == 0) {
// Append X, N times to
// the answer
Xs += n;
// Reduce N to zero
n = 0;
}
else {
// Reduce N by X
n -= X;
// Append Y, X times
// to the answer
Ys += X;
}
}
// If number can be formed
if (n == 0) {
while (Xs-- > 0)
cout << X;
while (Ys-- > 0)
cout << Y;
}
// Otherwise
else
cout << "-1";
}
// Driver Code
int main()
{
int n = 19, X = 7, Y = 5;
largestNumber(n, X, Y);
return 0;
}
Java
// Java program to implement the
// above approach
import java.util.*;
class GFG{
// Function to generate and return
// the largest number
public static void largestNumber(int n, int X,
int Y)
{
int maxm = Math.max(X, Y);
// Store the smaller in Y
Y = X + Y - maxm;
// Store the larger in X
X = maxm;
// Stores respective counts
int Xs = 0;
int Ys = 0;
while (n > 0)
{
// If N is divisible by Y
if (n % Y == 0)
{
// Append X, N times to
// the answer
Xs += n;
// Reduce N to zero
n = 0;
}
else
{
// Reduce N by X
n -= X;
// Append Y, X times
// to the answer
Ys += X;
}
}
// If number can be formed
if (n == 0)
{
while (Xs-- > 0)
System.out.print(X);
while (Ys-- > 0)
System.out.print(Y);
}
// Otherwise
else
System.out.print("-1");
}
// Driver code
public static void main (String[] args)
{
int n = 19, X = 7, Y = 5;
largestNumber(n, X, Y);
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program to implement
# the above approach
# Function to generate and return
# the largest number
def largestNumber(n, X, Y):
maxm = max(X, Y)
# Store the smaller in Y
Y = X + Y - maxm
# Store the larger in X
X = maxm
# Stores respective counts
Xs = 0
Ys = 0
while (n > 0):
# If N is divisible by Y
if (n % Y == 0):
# Append X, N times to
# the answer
Xs += n
# Reduce N to zero
n = 0
else:
# Reduce N by x
n -= X
# Append Y, X times to
# the answer
Ys += X
# If number can be formed
if (n == 0):
while (Xs > 0):
Xs -= 1
print(X, end = '')
while (Ys > 0):
Ys -= 1
print(Y, end = '')
# Otherwise
else:
print("-1")
# Driver code
n = 19
X = 7
Y = 5
largestNumber(n, X, Y)
# This code is contributed by himanshu77
C#
// C# program to implement the
// above approach
using System;
class GFG{
// Function to generate and return
// the largest number
public static void largestNumber(int n, int X,
int Y)
{
int maxm = Math.Max(X, Y);
// Store the smaller in Y
Y = X + Y - maxm;
// Store the larger in X
X = maxm;
// Stores respective counts
int Xs = 0;
int Ys = 0;
while (n > 0)
{
// If N is divisible by Y
if (n % Y == 0)
{
// Append X, N times to
// the answer
Xs += n;
// Reduce N to zero
n = 0;
}
else
{
// Reduce N by X
n -= X;
// Append Y, X times
// to the answer
Ys += X;
}
}
// If number can be formed
if (n == 0)
{
while (Xs-- > 0)
Console.Write(X);
while (Ys-- > 0)
Console.Write(Y);
}
// Otherwise
else
Console.Write("-1");
}
// Driver code
public static void Main (String[] args)
{
int n = 19, X = 7, Y = 5;
largestNumber(n, X, Y);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript program to implement the
// above approach
// Function to generate and return
// the largest number
function largestNumber(n, X, Y)
{
let maxm = Math.max(X, Y);
// Store the smaller in Y
Y = X + Y - maxm;
// Store the larger in X
X = maxm;
// Stores respective counts
let Xs = 0;
let Ys = 0;
while (n > 0)
{
// If N is divisible by Y
if (n % Y == 0)
{
// Append X, N times to
// the answer
Xs += n;
// Reduce N to zero
n = 0;
}
else
{
// Reduce N by X
n -= X;
// Append Y, X times
// to the answer
Ys += X;
}
}
// If number can be formed
if (n == 0)
{
while (Xs-- > 0)
document.write(X);
while (Ys-- > 0)
document.write(Y);
}
// Otherwise
else
document.write("-1");
}
// Driver Code
let n = 19, X = 7, Y = 5;
largestNumber(n, X, Y);
// This code is contributed by splevel62.
</script>
Producción:
7777755555555555555
Complejidad temporal: O(N)
Espacio auxiliar: O(1)