Рубрики

Найдите наименьшее число, цифры которого умножаются на данное число n

Математика

Учитывая число n, найдите наименьшее число p, так что если мы умножим все цифры p, мы получим n. Результат 'p' должен иметь минимум две цифры.

Примеры:

Input:  n = 36
Output: p = 49 
// Note that 4*9 = 36 and 49 is the smallest such number

Input:  n = 100
Output: p = 455
// Note that 4*5*5 = 100 and 455 is the smallest such number

Input: n = 1
Output:p = 11
// Note that 1*1 = 1

Input: n = 13
Output: Not Possible

Для данного n следующие два случая должны быть рассмотрены.
Случай 1: n <10 Когда n меньше 10, выход всегда равен n + 10. Например, для n = 7 выход составляет 17. Для n = 9 выход равен 19.

Случай 2: n> = 10 Найдите все факторы n, которые находятся между 2 и 9 (оба включительно). Идея состоит в том, чтобы начать поиск с 9, чтобы количество цифр в результате было минимизировано. Например, 9 предпочтительнее 33 и 8 предпочтительнее 24.
Сохраните все найденные факторы в массиве. Массив будет содержать цифры в порядке возрастания, поэтому, наконец, выведите массив в обратном порядке.

Ниже приводится реализация вышеуказанной концепции.

C / C ++

#include<stdio.h>

  
// Максимальное количество цифр в выводе
#define MAX 50

  
// выводит наименьшее число, цифры которого умножаются на n

void findSmallest(int n)

{

    int i, j=0;

    int res[MAX]; // Для сортировки цифр результата в обратном порядке

  

    // Случай 1: если число меньше 10

    if (n < 10)

    {

        printf("%d", n+10);

        return;

    }

  

    // Случай 2: начать с 9 и попробовать каждую возможную цифру

    for (i=9; i>1; i--)

    {

        // Если текущая цифра делит n, то сохраняем все

        // вхождения текущей цифры в res

        while (n%i == 0)

        {

            n = n/i;

            res[j] = i;

            j++;

        }

    }

  

    // Если n не может быть разбито в виде цифр (простые множители n

    // больше 9)

    if (n > 10)

    {

        printf("Not possible");

        return;

    }

  

    // Распечатать массив результатов в обратном порядке

    for (i=j-1; i>=0; i--)

        printf("%d", res[i]);

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    findSmallest(7);

    printf("\n");

  

    findSmallest(36);

    printf("\n");

  

    findSmallest(13);

    printf("\n");

  

    findSmallest(100);

    return 0;

}

Джава

// Java программа для поиска наименьшего числа
// цифры умножаются на заданное число n

  

import java.io.*;

  

class Smallest

{

    // Функция для печати наименьшего числа, чье

    // цифры умножаются на n

    static void findSmallest(int n)

    {

        int i, j=0;

        int MAX = 50;

        // Для сортировки цифр результата в обратном порядке

        int[] res = new int[MAX]; 

   

        // Случай 1: если число меньше 10

        if (n < 10)

        {

            System.out.println(n+10);

            return;

        }

   

        // Случай 2: начать с 9 и попробовать каждую возможную цифру

        for (i=9; i>1; i--)

        {

            // Если текущая цифра делит n, то сохраняем все

            // вхождения текущей цифры в res

            while (n%i == 0)

            {

                n = n/i;

                res[j] = i;

                j++;

            }

        }

   

        // Если n не может быть разбито в виде цифр (простые множители n

        // больше 9)

        if (n > 10)

        {

            System.out.println("Not possible");

            return;

        }

   

        // Распечатать массив результатов в обратном порядке

        for (i=j-1; i>=0; i--)

            System.out.print(res[i]);

        System.out.println();

    }

      

    // Драйвер программы

    public static void main (String[] args) 

    {

        findSmallest(7);

        findSmallest(36);

        findSmallest(13);

        findSmallest(100);

    }

}

  
// Предоставлено Прамод Кумар

питон

# Python код для поиска наименьшего числа
# чьи цифры умножаются, чтобы дать n

  
# функция для печати наименьшего числа которого
Количество цифр умножается на n

def findSmallest(n):

    # Случай 1 - Если число меньше 10

    if n < 10:

        print n+10

        return

      

    # Случай 2 - Начните с 9 и попробуйте все возможные цифры

    res = [] # сортировать цифры

    for i in range(9,1,-1):

        # Если текущая цифра делит n, то сохранить все

        # вхождения текущей цифры в res

        while n % i == 0:

            n = n / i

            res.append(i)

      

    # Если n не может быть разбит в виде цифр

    # простые множители n больше 9

      

    if n > 10:

        print "Not Possible"

        return

          

    # Вывести число из массива результатов в обратном порядке

    n = res[len(res)-1]

    for i in range(len(res)-2,-1,-1):

        n = 10 * n + res[i]

    print n

      
Код водителя

findSmallest(7)

  

findSmallest(36)

  

findSmallest(13)

  

findSmallest(100)

  
# Этот код предоставлен Harshit Agrawal

C #

// C # программа для поиска наименьшего числа
// цифры умножаются на заданное число n

using System;

  

class GFG {

      

    // Функция для печати наименьшего числа

    // чьи цифры умножаются на n

    static void findSmallest(int n)

    {

          

        int i, j=0;

        int MAX = 50;

          

        // чтобы забить цифры результата в

        // обратный порядок

        int []res = new int[MAX]; 

  

        // Случай 1: если число меньше 10

        if (n < 10)

        {

            Console.WriteLine(n + 10);

            return;

        }

  

        // Случай 2: начать с 9 и попробовать каждый

        // возможная цифра

        for (i = 9; i > 1; i--)

        {

              

            // Если текущая цифра делит n, то

            // сохраняем все вхождения текущего

            // цифра в рез

            while (n % i == 0)

            {

                n = n / i;

                res[j] = i;

                j++;

            }

        }

  

        // Если n не может быть разбит в форме

        // цифры (простые множители n

        // больше 9)

        if (n > 10)

        {

            Console.WriteLine("Not possible");

            return;

        }

  

        // Распечатать массив результатов в обратном порядке

        for (i = j-1; i >= 0; i--)

            Console.Write(res[i]);

              

        Console.WriteLine();

    }

      

    // Драйвер программы

    public static void Main () 

    {

        findSmallest(7);

        findSmallest(36);

        findSmallest(13);

        findSmallest(100);

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для поиска
// наименьшее число которого
// цифры умножаются на
// заданное число n печатает
// наименьшее число, чьи цифры
// умножаем на n

  

function findSmallest($n)

{

      

    // чтобы болеть цифры

    // результат в обратном порядке

    $i;

    $j = 0;

    $res; 

  

    // Случай 1: если число

    // меньше 10

    if ($n < 10)

    {

        echo $n + 10;

        return;

    }

  

    // Случай 2: начать с 9 и

    // пробуем каждую возможную цифру

    for ($i = 9; $i > 1; $i--)

    {

          

        // Если текущая цифра делится

        // n, затем сохраняем все

        // вхождения текущего

        // цифра в рез

        while ($n % $i == 0)

        {

            $n = $n / $i;

            $res[$j] = $i;

            $j++;

        }

    }

  

    // Если n не может быть сломано

    // в виде цифр

    // (простые множители n

    // больше 9)

    if ($n > 10)

    {

        echo "Not possible";

        return;

    }

  

    // Распечатать результат

    // массив в обратном порядке

    for ($i = $j - 1; $i >= 0; $i--)

        echo $res[$i];

}

  

    // Код драйвера

    findSmallest(7);

    echo "\n";

  

    findSmallest(36);

      

    echo "\n";

  

    findSmallest(13);

    echo "\n";

  

    findSmallest(100);

  
// Этот код предоставлен ajit
?>


Выход:

17
49
Not possible
455

Эта статья предоставлена Ashish Bansal . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Найдите наименьшее число, цифры которого умножаются на данное число n

0.00 (0%) 0 votes