Dado un número entero N , la tarea es encontrar el número más pequeño mayor o igual que N tal que sea divisible por todos sus dígitos distintos de cero.
Ejemplos:
Entrada: N = 31
Salida: 33
Explicación: 33 es el número más pequeño que satisface la condición dada.
En el lugar de la Unidad: 33%3 = 0
En el lugar de Uno: 33%3 = 0Entrada: N = 30
Salida: 30
Explicación: 30 es el número más pequeño que satisface la condición dada.
En casa de uno: 30%3 = 0
Método: el número más pequeño que es divisible por todos los dígitos del 1 al 9 es igual al MCM de (1, 2, 3, 4, 5, 6, 7, 8, 9) = 2520. Por lo tanto, los múltiplos de 2520 también son divisible por todos los dígitos del 1 al 9 , lo que implica que (N + 2520) siempre cumplirá la condición. Por lo tanto, itere en el rango [N, 2520 + N] y busque el número más pequeño que satisfaga la condición dada. Siga los pasos a continuación para resolver el problema:
- Inicialice ans como 0 para almacenar el número más pequeño mayor o igual a N de modo que sea divisible por todos sus dígitos distintos de cero.
- Iterar sobre el rango [N, N + 2520] usando la variable i .
- Inicialice una variable posible como 1 para verificar si el número actual i satisface la condición dada o no.
- Obtenga todos los dígitos distintos de cero de i y verifique si i es divisible por cada uno de ellos. Si se encuentra que es cierto, entonces actualice posible a 1 , y actualice ans como i , y salga del bucle .
- Después de los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the smallest number
// greater than or equal to N such that
// it is divisible by its non-zero digits
void findSmallestNumber(int n)
{
// Iterate in range[N, N + 2520]
for (int i = n; i <= (n + 2520); ++i) {
// To check if the current number
// satisfies the given condition
bool possible = 1;
// Store the number in a temporary
// variable
int temp = i;
// Loop until temp > 0
while (temp) {
// Check only for non zero digits
if (temp % 10 != 0) {
// Extract the current digit
int digit = temp % 10;
// If number is divisible
// by current digit or not
if (i % digit != 0) {
// Otherwise, set
// possible to 0
possible = 0;
// Break out of the loop
break;
}
}
// Divide by 10
temp /= 10;
}
if (possible == 1) {
cout << i;
return;
}
}
}
// Driver Code
int main()
{
int N = 31;
// Function Call
findSmallestNumber(N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the smallest number
// greater than or equal to N such that
// it is divisible by its non-zero digits
static void findSmallestNumber(int n)
{
// Iterate in range[N, N + 2520]
for(int i = n; i <= (n + 2520); ++i)
{
// To check if the current number
// satisfies the given condition
int possible = 1;
// Store the number in a temporary
// variable
int temp = i;
// Loop until temp > 0
while (temp != 0)
{
// Check only for non zero digits
if (temp % 10 != 0)
{
// Extract the current digit
int digit = temp % 10;
// If number is divisible
// by current digit or not
if (i % digit != 0)
{
// Otherwise, set
// possible to 0
possible = 0;
// Break out of the loop
break;
}
}
// Divide by 10
temp /= 10;
}
if (possible == 1)
{
System.out.println(i);
return;
}
}
}
// Driver code
public static void main(String[] args)
{
int N = 31;
// Function Call
findSmallestNumber(N);
}
}
// This code is contributed by susmitakundugoaldanga
Python3
# Python3 program for the above approach # Function to find the smallest number # greater than or equal to N such that # it is divisible by its non-zero digits def findSmallestNumber(n): # Iterate in range[N, N + 2520] for i in range(n, n + 2521): # To check if the current number # satisfies the given condition possible = 1 # Store the number in a temporary # variable temp = i # Loop until temp > 0 while (temp): # Check only for non zero digits if (temp % 10 != 0): # Extract the current digit digit = temp % 10 # If number is divisible # by current digit or not if (i % digit != 0): # Otherwise, set # possible to 0 possible = 0 # Break out of the loop break # Divide by 10 temp //= 10 if (possible == 1): print(i, end = "") return # Driver Code if __name__ == "__main__" : N = 31 # Function Call findSmallestNumber(N) # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the smallest number
// greater than or equal to N such that
// it is divisible by its non-zero digits
static void findSmallestNumber(int n)
{
// Iterate in range[N, N + 2520]
for(int i = n; i <= (n + 2520); ++i)
{
// To check if the current number
// satisfies the given condition
int possible = 1;
// Store the number in a temporary
// variable
int temp = i;
// Loop until temp > 0
while (temp != 0)
{
// Check only for non zero digits
if (temp % 10 != 0)
{
// Extract the current digit
int digit = temp % 10;
// If number is divisible
// by current digit or not
if (i % digit != 0)
{
// Otherwise, set
// possible to 0
possible = 0;
// Break out of the loop
break;
}
}
// Divide by 10
temp /= 10;
}
if (possible == 1)
{
Console.Write(i);
return;
}
}
}
// Driver code
public static void Main(String[] args)
{
int N = 31;
// Function Call
findSmallestNumber(N);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// javascript program for the above approach
// Function to find the smallest number
// greater than or equal to N such that
// it is divisible by its non-zero digits
function findSmallestNumber(n)
{
// Iterate in range[N, N + 2520]
for(i = n; i <= (n + 2520); ++i)
{
// To check if the current number
// satisfies the given condition
var possible = 1;
// Store the number in a temporary
// variable
var temp = i;
// Loop until temp > 0
while (temp != 0)
{
// Check only for non zero digits
if (temp % 10 != 0)
{
// Extract the current digit
var digit = temp % 10;
// If number is divisible
// by current digit or not
if (i % digit != 0)
{
// Otherwise, set
// possible to 0
possible = 0;
// Break out of the loop
break;
}
}
// Divide by 10
temp = parseInt(temp / 10);
}
if (possible == 1)
{
document.write(i);
return;
}
}
}
// Driver code
var N = 31;
// Function Call
findSmallestNumber(N);
// This code is contributed by shikhasingrajput
</script>
Producción:
33
Complejidad de tiempo: O(2520*log 10 N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shreyasshetty788 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA