Найдите N-значное число, которое не делится ни на одну из его цифр.

Опубликовано: 11 Января, 2022

Учитывая целое число N, задача состоит в том, чтобы найти такое N-значное число, которое не делится ни на одну из его цифр.
Примечание: для каждого значения N. может быть несколько ответов.

Примеры:

Input: N = 4 
Output: 6789 
Explanation: 
As the number 6789 is not divisible by any of its digits, it is 6, 7, 8 and 9 and it is also a four-digit number. Hence, it can be the desired number. 

Input: N = 2 
Output: 57 
Explanation: 
As the number 57 is not divisible by any of its digits, it is 5 and 7 and it is also a 2-digit number. Hence, it can be the desired number.   

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: ключевое наблюдение в проблеме состоит в том, что 2 и 3 - это числа, которые не делят друг друга. Кроме того, числа «23, 233, 2333,…» не делятся ни на 2, ни на 3. Следовательно, для любого N-значного числа старшая цифра будет 2, а остальные цифры будут 3, чтобы получить желаемый номер.

Алгоритм:

  • Проверьте, равно ли значение N 1, тогда такое число невозможно, поэтому верните -1.
  • В противном случае инициализируйте переменную num , чтобы сохранить число как 2.
  • Выполните цикл от 1 до N, а затем для каждой итерации умножьте число на 10 и прибавьте к нему 3.
 число = (число * 10) + 3

Below is the implementation of the above approach: 

C++

// C++ implementation to find a
// N-digit number such that the number
// it is not divisible by its digits
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
 
// Function to find the number
// such that it is not divisible
// by its digits
void solve(ll n)
{
    // Base Cases
    if (n == 1)
    {
        cout << -1;
    }
    else {
         
        // First Digit of the
        // number will be 2
        int num = 2;
         
        // Next digits of the numbers
        for (ll i = 0; i < n - 1; i++) {
            num = (num * 10) + 3;
        }
        cout << num;
    }
}
 
// Driver Code
int main()
{
    ll n = 4;
     
    // Function Call
    solve(n);
}

Java

// Java implementation to find a
// N-digit number such that the number
// it is not divisible by its digits
class GFG {
 
    long ll;
     
    // Function to find the number
    // such that it is not divisible
    // by its digits
    static void solve(long n)
    {
        // Base Cases
        if (n == 1)
        {
            System.out.println(-1);
        }
        else {
             
            // First Digit of the
            // number will be 2
            int num = 2;
             
            // Next digits of the numbers
            for (long i = 0; i < n - 1; i++) {
                num = (num * 10) + 3;
            }
            System.out.println(num);
        }
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        long n = 4;
         
            // Function Call
            solve(n);
    }
}
 
// This code is contributed by AnkitRai01

Python3

# Python3 implementation to find a
# N-digit number such that the number
# it is not divisible by its digits
 
# Function to find the number
# such that it is not divisible
# by its digits
def solve(n) :
 
    # Base Cases
    if (n == 1) :
 
        print(-1);
     
    else :
         
        # First Digit of the
        # number will be 2
        num = 2;
         
        # Next digits of the numbers
        for i in range(n - 1) :
            num = (num * 10) + 3;
          
        print(num);
 
# Driver Code
if __name__ == "__main__" :
 
    n = 4;
     
    # Function Call
    solve(n);
     
# This code is contributed by AnkitRai01

C#

// C# implementation to find a
// N-digit number such that the number
// it is not divisible by its digits
using System;
 
class GFG {
  
    long ll;
      
    // Function to find the number
    // such that it is not divisible
    // by its digits
    static void solve(long n)
    {
        // Base Cases
        if (n == 1)
        {
            Console.WriteLine(-1);
        }
        else {
              
            // First Digit of the
            // number will be 2
            int num = 2;
              
            // Next digits of the numbers
            for (long i = 0; i < n - 1; i++) {
                num = (num * 10) + 3;
            }
            Console.WriteLine(num);
        }
    }
      
    // Driver Code
    public static void Main(String[] args)
    {
        long n = 4;
          
            // Function Call
            solve(n);
    }
}
 
// This code is contributed by sapnasingh4991

Javascript

<script>
//Javascript  implementation to find a
// N-digit number such that the number
// it is not divisible by its digits
 
 
// Function to find the number
// such that it is not divisible
// by its digits
function solve(n)
{
    // Base Cases
    if (n == 1)
    {
        document.write(  -1);
    }
    else {
         
        // First Digit of the
        // number will be 2
        var num = 2;
         
        // Next digits of the numbers
        for (var i = 0; i < n - 1; i++) {
            num = (num * 10) + 3;
        }
        document.write(  num);
    }
}
 
 
// Given N
var n = 4;
// Function Call
solve(n);
 
// This code is contributed by SoumikMondal
</script>
Output: 
2333

 

Анализ производительности:

  • Сложность времени: O (N).
  • Вспомогательное пространство: O (1).

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.