Dados tres enteros positivos N , M y X , la tarea es generar un número agregando X dígitos en el lado derecho de N de modo que el número sea divisible por M . Si existen varias soluciones, imprima cualquiera de ellas. De lo contrario, imprima -1 .
Ejemplos:
Entrada: N = 10, M = 5, X = 4
Salida: 105555
Explicación: Uno de los posibles valores de N (= 10) agregando X (= 4) dígitos en el lado derecho de N es 105555, que es divisible por M (= 5).Entrada: N = 4, M = 50, X = 2
Salida: 400
Enfoque: la idea es agregar X dígitos en el lado derecho de N probando todos los dígitos posibles del rango [0, 9] y después de agregar X dígitos en el lado derecho de N, verifique si el número es divisible por M o no. Si se encuentra que es cierto, imprima el número. De lo contrario, imprima -1 . Las siguientes son las relaciones de recurrencia:
Siga los pasos a continuación para resolver el problema:
- Use la relación de recurrencia anterior, verifique si el número N es divisible por M o no agregando X dígitos en el lado derecho de N. Si se determina que es cierto, imprima el valor de N agregando X dígitos.
- De lo contrario, imprima -1 .
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 check if the value of N by
// appending X digits on right side of N
// is divisible by M or not
bool isDiv(int N, int X, int M, int& res)
{
// Base Case
if (X == 0) {
// If N is divisible
// by M
if (N % M == 0) {
// Update res
res = N;
return true;
}
return false;
}
// Iterate over the range [0, 9]
for (int i = 0; i <= 9; i++) {
// If N is divisible by M by
// appending X digits
if (isDiv(N * 10 + i, X - 1, M, res)) {
return true;
}
}
}
// Driver Code
int main()
{
int N = 4, M = 50, X = 2;
// Stores the number by appending
// X digits on the right side of N
int res = -1;
isDiv(N, X, M, res);
cout << res;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to check if the value of N by
// appending X digits on right side of N
// is divisible by M or not
static int isDiv(int N, int X, int M, int res)
{
// Base Case
if (X == 0)
{
// If N is divisible
// by M
if (N % M == 0)
{
// Update res
res = N;
return res;
}
return res;
}
// Iterate over the range [0, 9]
for (int i = 0; i < 9; i++)
{
// If N is divisible by M by
// appending X digits
int temp = isDiv(N * 10 + i, X - 1, M, res);
if (temp != -1)
{
return temp;
}
}
return res;
}
// Driver code
public static void main(String[] args)
throws java.lang.Exception
{
int N = 4, M = 50, X = 2;
// Stores the number by appending
// X digits on the right side of N
int res = -1;
res = isDiv(N, X, M, res);
System.out.println(res);
}
}
// This code is contributed by 18bhupenderyadav18.
Python3
# Python3 program to implement
# the above approach
# Function to check if the value of N by
# appending X digits on right side of N
# is divisible by M or not
# global variable to store result
res = -1
def isDiv(N, X, M):
# Base case
if(X == 0):
# If N is divisible
# by M
if(N % M == 0):
global res
res = N
return True
return False
# Iterate over the range [0, 9]
for i in range(10):
# if N is Divisible by M upon appending X digits
if(isDiv(N*10+i, X-1, M)):
return True
# Driver Code
if __name__ == "__main__":
N, M, X = 4, 50, 2
if(isDiv(N, X, M)):
print(res)
else:
print("-1")
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to check if the value of N by
// appending X digits on right side of N
// is divisible by M or not
static int isDiv(int N, int X, int M, int res)
{
// Base Case
if (X == 0)
{
// If N is divisible
// by M
if (N % M == 0)
{
// Update res
res = N;
return res;
}
return res;
}
// Iterate over the range [0, 9]
for (int i = 0; i < 9; i++)
{
// If N is divisible by M by
// appending X digits
int temp = isDiv(N * 10 + i, X - 1, M, res);
if (temp != -1)
{
return temp;
}
}
return res;
}
// Driver code
public static void Main()
{
int N = 4, M = 50, X = 2;
// Stores the number by appending
// X digits on the right side of N
int res = -1;
res = isDiv(N, X, M, res);
Console.WriteLine(res);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program to implement
// the above approach
var res = -1;
// Function to check if the value of N by
// appending X digits on right side of N
// is divisible by M or not
function isDiv(N, X, M)
{
// Base Case
if (X == 0) {
// If N is divisible
// by M
if (N % M == 0) {
// Update res
res = N;
return true;
}
return false;
}
// Iterate over the range [0, 9]
for (var i = 0; i <= 9; i++) {
// If N is divisible by M by
// appending X digits
if (isDiv(N * 10 + i, X - 1, M)) {
return true;
}
}
}
// Driver Code
var N = 4, M = 50, X = 2;
// Stores the number by appending
// X digits on the right side of N
isDiv(N, X, M, res);
document.write(res);
</script>
400
Complejidad temporal: O(10 X )
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ananyadixit8 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA