Take the 2-minute tour ×

I made a program to solve this problem from the ACM.

Matchsticks are ideal tools to represent numbers. A common way to represent the ten decimal digits with matchsticks is the following:

This is identical to how numbers are displayed on an ordinary alarm clock. With a given number of matchsticks you can generate a wide range of numbers. We are wondering what the smallest and largest numbers are that can be created by using all your matchsticks.



One line with an integer n (2 ≤ n ≤ 100): the number of matchsticks you have. Output

Per testcase:

One line with the smallest and largest numbers you can create, separated by a single space. Both numbers should be positive and contain no leading zeroes. Sample Input

4 3 6 7 15 Sample Output

7 7 6 111 8 711 108 7111111

The problem is that it's way too slow to solve it for 100 matchsticks. The search tree is too big to bruteforce it.

Here are the results for the first 10:

2: 1 1

3: 7 7

4: 4 11

5: 2 71

6: 6 111

7: 8 711

8: 10 1111

9: 18 7111

10: 22 11111

The pattern for the maximums is easy but I don't see a shortcut for the minimums. Can someone suggest a better way to solve this problem? Here is the code I used:

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

    #define MAX 20 //should be 100

    //match[i] contains number of matches needed to form i
    int match[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
    string mi[MAX+1], ma[MAX+1];
    char curr[MAX+1] = "";

    //compare numbers saved as strings
    int mycmp(string s1, string s2)
        int n = (int)s1.length();
        int m = (int)s2.length();
        if (n != m)
            return n - m;
            return s1.compare(s2);

    //i is the current digit, used are the number of matchsticks so far
    void fill(int i, int used)
        //check for smaller and bigger values
        if (mycmp(curr, mi[used]) < 0) mi[used] = curr;
        if (mycmp(curr, ma[used]) > 0) ma[used] = curr;

        //recurse further, don't start numbers with a zero
        for (int a = i ? '0' : '1'; a <= '9'; a++) {
            int next = used + match[a-'0'];
            if (next <= MAX) {
                curr[i] = a;
                curr[i+1] = '\0';
                fill(i + 1, next);

    int main()
            mi[i] = string(MAX, '9');
            ma[i] = "0";

        //precalculate the values
        fill(0, 0);

        int n;
        cin >> n;

        //print those that were asked
        while (n--) {
            int num;
            cin >> num;
            cout << mi[num] << " " << ma[num] << endl;

        return 0;

EDIT : I ended up using the dynamic programming solution. I tried it with dp before but I was messing around with a two-dimensional state array. The solutions here are much better. Thanks!

share|improve this question
That's the problem with recursion. While I am not very sure if it applies to your problem but have you heard of "dynamic programming?" Most of the programming competition questions actually require a dynamic programming solution. –  Jaywalker Jul 21 '11 at 12:55
The result can be obtained in linear complexity. See my answer. –  Benoît Jul 21 '11 at 14:45
This question is now useless because the offsite link is now dead. This just goes to show why you shouldn't link to offsite questions without summarising them in the post. –  Robin Green Dec 30 '13 at 11:41

4 Answers 4

up vote 2 down vote accepted

In order to find the result :

  • first find the minimal number of digits for smallest number
  • then proceed from most significant digit to the least significant one.

Every digit should be chosen so that there exists a solution for remaining digits. Each digit requires between 2 and 7 matches. So you must choose the smallest Nth "top" digit that leaves the number of remaining matches between 2*(N-1) and 7*(N-1).

Do not forget that 0 has to be excluded from the search for the most significant digit of the result.

As a sidenote, one reason which makes this algorithm work is the fact that there is at least one corresponding digit for every value (of matches) between 2 and 7.

EDIT : example for 10 matches 10 matches --> 2 digits
Acceptable number of matches for top digit = between 3 and 7.
Smallest digit which requires between 3 and 7 matches -> 2 (which takes 5 matches), 0 being excluded.
Chosen first digit = 2

5 remaining matches -->
Acceptable number of matches for second (and in this case last) digit = exactly 5
Smallest digit which requires 5 matches -> 2
Chosen second digit = 2

Result = 22.

EDIT code for this problem

#include <iostream>
#include <vector>

std::vector<int> nbMatchesForDigit;

long long minNumberForMatches(unsigned int nbMatches)
    int nbMaxMatchesForOneDigit = 7;
    int nbMinMatchesForOneDigit = 2;
    int remainingMatches = nbMatches;
    int nbDigits = 1 + nbMatches / nbMaxMatchesForOneDigit; 
    long long result = 0;
    for (int idDigit = 0 ; idDigit < nbDigits ; ++idDigit )
        int minMatchesToUse = std::max(nbMinMatchesForOneDigit, remainingMatches - nbMaxMatchesForOneDigit * (nbDigits - 1 - idDigit));
        int maxMatchesToUse = std::min(nbMaxMatchesForOneDigit, remainingMatches - nbMinMatchesForOneDigit * (nbDigits - 1 - idDigit));
        for (int digit = idDigit > 0 ? 0 : 1 ; digit <= 9 ; ++digit )
            if( nbMatchesForDigit[digit] >= minMatchesToUse && 
                nbMatchesForDigit[digit] <= maxMatchesToUse )
                result = result * 10 + digit;
                remainingMatches -= nbMatchesForDigit[digit];
    return result;

int main()

    for( int i = 2 ; i <= 100 ; ++i )
        std::cout << i << " " << minNumberForMatches(i) << std::endl;
share|improve this answer
I don't think a greedy algorithm will work in this case. Pretty sure this is an example of a Knapsack problem –  R0MANARMY Jul 21 '11 at 13:15
What do you mean by "proceed from most significant digit to the least significant one"? How exactly do you fill them in? I think that's rather non-trivial. –  tskuzzy Jul 21 '11 at 13:19
If I understand correctly, then it doesn't work ; suppose you have ten matches. Your algorithm (it's a greedy one) will pick 8, then 7, returning 78. But with ten matches, 35 and 22 are better solutions. –  Clément Jul 21 '11 at 13:49
I guess i haven't been clear describing my algorithm : see the example in my answer. –  Benoît Jul 21 '11 at 14:01
Nice and clean solution! –  Jasper Jul 21 '11 at 14:40

You can use a dynamic programming solution.

Suppose that you have n matches, and you know how to solve the problem (minimum number) for all set of n-k matches, where k takes all the values corresponding to the number of matches that each number uses (2 for 1, 5 for 3, etc.)

The solution is then derived recursively. Supposing that you end your number with a one (in the least significant position), then the best solution is obtained by writing (best solution with n-2 matches) 1. Supposing you end it with a two, the best solution is (best solution with n-5 matches) 2. And so on ; eventually you can compare these ten numbers, and pick the best one.

So now, all you have to do is devise the best solution for all n smaller than your input, recursively.

EDIT: If you implement this algorithm in a straightforward way, you'll end up with an exponential complexity. The trick here is to notice that if your core function MinimumGivenNMatches, only takes one parameter, n. Hence you'll end up calling it with the same values a huge number of times.

To make the complexity linear, you just need to memoize (ie. remember) the solution for each n, using an auxiliary array.

share|improve this answer
Elegant solution. –  Benoît Jul 21 '11 at 13:41
Thanks! As an additional remark, the corresponding best solution can be found by keeping an additional array, predecessor; you just have to modify the main loop to keep track of the calls. –  Clément Jul 21 '11 at 13:43
Just a nitpick, but the dynamic programming method of remembering things is memoize as in memoization, not memorize. Good answer, though. +1 –  Bradley Swain Jul 21 '11 at 14:52
Sorry, that was my mistake ! –  Benoît Jul 21 '11 at 15:01

Use dynamic programming instead of recursion. It's significantly faster to store calculated values and re-use them. In fact, it turns an exponential running time into a polynomial one.

The basic idea is to have an array min which keeps track of the minimum number that can be made using exactly n matchsticks. So

min[0] = ""
min[1] = infinity
min[2] = "1"
min[3] = min("1+"min[3-2],"7")
min[4] = min("1"+min[4-2],"7"+min[4-3])
share|improve this answer
The complexity of the optimal solution is linear. See my answer. –  Benoît Jul 21 '11 at 14:21
This is linear. –  tskuzzy Jul 21 '11 at 15:19
right, sorry. I am not sure how you would program this algorithm efficiently, though. –  Benoît Jul 21 '11 at 15:44
My solution is the same as Clément's. Basically just loop through values 0 to N of min, calculating each element. Then your answer is just min[N]. –  tskuzzy Jul 21 '11 at 16:09

For the minima, note that because no leading zeros are allowed, you want to minimize the number of digits. The minimal number of digits is ceil(n/7).

Then it's quite easy to calculate the minimum number of matchsticks which MUST be used in the leading digit, from that you get the smallest possible value of the leading digit.

share|improve this answer

Your Answer


