Número más pequeño mayor o igual a N que es divisible por sus dígitos distintos de cero

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 = 0

Entrada: 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *