Smallest Number With Given Digit Product - Practice Coding Problems

Smallest Number With Given Digit Product - Problem

Math Greedy Medium

Given a positive integer n, return a string representing the smallest positive integer such that the product of its digits is equal to n.

If no such number exists, return "-1".

Note: The returned number should be as small as possible, which means it should have the fewest digits, and among numbers with the same number of digits, it should be lexicographically smallest.

Input & Output

Example 1 — Basic Case

$ Input: n = 12

› Output: 26

💡 Note: We need digits that multiply to 12. Using greedy approach: 12 = 6 × 2. Sort digits: [2,6] → "26"

Example 2 — Single Digit

$ Input: n = 1

› Output: 1

💡 Note: Special case: the smallest number with digit product 1 is 1 itself

Example 3 — Impossible Case

$ Input: n = 11

› Output: -1

💡 Note: 11 is prime and > 9, so it cannot be expressed as a product of single digits (2-9)

Constraints

1 ≤ n ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Target product n = 12

Factorize

Break into digit factors: 12 = 6 × 2

Output

Smallest arrangement: "26"

Key Takeaway

🎯 Key Insight: Use greedy factorization with largest digits first, then sort ascending for the smallest possible number

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use greedy factorization with digits 9 down to 2, then sort the result digits in ascending order. This approach ensures we use the fewest digits possible (by using larger digits first) and get the lexicographically smallest result. Time: O(log n), Space: O(log n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Factorization	O(log n)	O(log n)	Break n into prime factors and greedily use largest possible digits (9,8,7...2)
Brute Force	O(10^k)	O(1)	Try every number starting from 1 until finding one with digit product equal to n

Greedy Factorization — Algorithm Steps

Handle special cases (n=0 returns '10', n=1 returns '1')
For digits 9 down to 2, divide n by digit as many times as possible
Collect all used digits and sort them in ascending order
If n becomes 1, return the sorted digits as string, else return '-1'

Visualization

Tap to expand

Step-by-Step Walkthrough

Factor with 9

Use digit 9 as many times as possible

Factor with smaller digits

Continue with 8,7,6,5,4,3,2

Sort and combine

Sort digits ascending for smallest number

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

char* solution(int n) {
    char* result = (char*)malloc(100);
    
    if (n == 0) {
        strcpy(result, "10");
        return result;
    }
    if (n == 1) {
        strcpy(result, "1");
        return result;
    }
    
    int digits[100];
    int count = 0;
    
    // Try digits from 9 down to 2
    for (int digit = 9; digit >= 2; digit--) {
        while (n % digit == 0) {
            digits[count++] = digit;
            n /= digit;
        }
    }
    
    // If n is not 1, then n has prime factors > 9
    if (n > 1) {
        strcpy(result, "-1");
        return result;
    }
    
    // Sort digits in ascending order to get smallest number
    qsort(digits, count, sizeof(int), compare);
    
    int pos = 0;
    for (int i = 0; i < count; i++) {
        pos += sprintf(result + pos, "%d", digits[i]);
    }
    result[pos] = '\0';
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    char* result = solution(n);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

We divide n by digits 9,8,7,6,5,4,3,2 at most log n times total

⚡ Linearithmic

Space Complexity

O(log n)

Store the digits in result array, at most log n digits needed

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Factorization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler