A smallest number - June Circuits '21 HackerEarth solution | AskTheCode

HackerEarth June Circuits '21 solution | A Smallest Number Circuits '21 Solution | AskTheCode

---

Problem:

You are given an integer K.

Find the smallest number N such that N has exactly K digits and none of the digits in N is $$0$$. Also, the product of digits in number N is greater than or equal to the sum of digits in number N.

---

Input format:

• The first line contains an integer T denoting the number of test cases.

• For each test case, the first line contains an integer K.

Output format:

For each test case in a new line print the smallest number N that satisfies the given condition.

Constraints:

• 1 <= T <= 10

• 1 <= K <= 5 x 10^5

---

Sample Input:

2
1
3

Sample Output:

1
123

---

EXPLANATION:

For first test case, N = 1 is the smallest number which has product of digits i.e. 1 greater than or equal to sum of digits i.e. 1.

For second test case, N = 123 is the smallest number which has product of digits i.e. 6 greater than or equal to sum of digits i.e. 6.

---

Code:

#include<bits/stdc++.h>
#define int long long int
using namespace std;
int sum, product;

int get_digits(int num){
    int answer = 0;
    while(num){
        num /= 10;
        answer++;
    }
    return answer;
}

bool check(int num){
    sum = 0;
    product = 1;
    while(num){
        sum += (num%10);
        product *= (num%10);
        num /= 10;
    }
    return (product >= sum);
}

void solve(){
    int k;
    cin >> k;
    assert(1 <= k and k <= 500000);

    if(k <= 6){
        for(int i = 1 ; i < 1000000 ; i++){
            if(check(i) and get_digits(i) == k){
                cout << i << endl;
                return;
            }
        }
    }
    else{
        for(int i = 1 ; i < 1000000 ; i++){
            check(i);
            if(product >= sum + k - get_digits(i)){
                for(int j = 1 ; j <= (k - get_digits(i)) ; j++){
                    cout << 1;
                }
                cout << i << endl;
                return;
            }
        }
    }
}
signed main(){
    int t;
    cin >> t;
    assert(1 <= t and t <= 10);
    while(t--){
        solve();
    }
}