samedi 19 mai 2018

Find the smallest number whose digits multiply to a given number

(beginner here)

My task says I have to find the smallest number whose digits multiply to a given number. If such number cannot be made output "-1"

Example:

10 = 25       2*5=10
13 = -1  
5 = 5     
100 = 455     4*5*5 = 100

input is a single number n;

My code seems to work fine, but whenever I try to upload it to a contest website my code doesn't pass all the test cases. All test cases are hidden so I don't know the specific test case my code fails.

So I wanted to ask for help, I want to know how can I find a specific that specific test case or even better help me find that test case.

My code is based on code from these websites:

https://www.geeksforgeeks.org/smallest-number-k-product-digits-k-equal-n/

https://www.geeksforgeeks.org/find-smallest-number-whose-digits-multiply-given-number-n/

My code:

#include <iostream>
#include <stack>
using namespace std;

    // function to find smallest number k such that
    // the product of digits of k is equal to n
    long long int smallestNumber(long long int n)
    {
        // if 'n' is a single digit number, then
        // it is the required number
        if (n >= 0 && n <= 9)
            return n;

        // stack the store the the digits
        stack<long long int> digits;

        // repeatedly divide 'n' by the numbers 
        // from 9 to 2 until all the numbers are 
        // used or 'n' > 1
        for (long long int i = 9; i >= 2 && n > 1; i--)
        {
            while (n % i == 0)
            {
                // save the digit 'i' that divides 'n'
                // onto the stack
                digits.push(i);
                n = n / i;
            }
        }

        // if true, then no number 'k' can be formed 
        if (n != 1)
            return -1;

        // pop digits from the stack 'digits'
        // and add them to 'k'
        long long int k = 0;
        while (!digits.empty())
        {
            k = k * 10 + digits.top();
            digits.pop();
        }

        // required smallest number
        return k;
    }

    // Driver program to test above
    int main()
    {
        long long int n;//number i want to convert
        cin >> n;
        cout << smallestNumber(n);
        return 0;
    }

Thank you.

Aucun commentaire:

Enregistrer un commentaire