Program for Lucky Numbers (4, 7, 44, 47, 74, 77, 444, ...)

Question

I am studying algorithm problem solving.

One question is so difficult for me.

Could anyone give me some hint for this problem?

Below is problem description.

Some numbers can be made by summing up the "LUCKY Numbers". (LUCKY Numbers consists of only "4" and "7". ex 4, 7, 44, 47, 74, 77, 444, 447, 474, ... )

When N is given, write a program that prints the LUCKY Numbers which a sum of N.

If there are several method, print smaller numbers of one. (ex. when N is 28, 28 = 7 + 7 + 7 + 7 OR 28 = 4 + 4 + 4 + 4 + 4 + 4 + 4) but smaller numbers of LUCKY Numbers is 7 + 7 + 7 + 7.

If there are several methods, output lexicographically the most preceding one. (ex. when N is 11, 11 = 4 + 7 OR 7 + 4) but lexicographically preceding LUCKY Numbers is 4 + 7.

If N is not expressible as the sum of LUCKY Numbers, output -1. (ex. when N is 10, 10 is not represented using LUCKY Numbers.)

1 <= N <= 1000000000

I wrote C++ code. However, when N is big, my program exceeds Time Limit (2 seconds).

• smaller N : 11111, 55555, ... MY program works well.

• bigger N : ..., 999999999, 1000000000 MY program exceeds Time Limit.

Below is my source code.

#include <cstdio>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long lld;

const lld MAXN = 1e9;
vector<lld> V;

map<lld, lld> M;

//      make LUCKY Numbers
void dfs(lld n) {
    if (n > MAXN)
        return;

    V.push_back(n);
    dfs(n * 10 + 4);
    dfs(n * 10 + 7);
}

void reconstruct(lld current) {
    //      base case.
    if (current == 0LL) {
        return;
    }

    lld previous = M.find(current)->second;
    reconstruct(previous);
    printf("%lld ", current - previous);
}

int main(int argc, char* argv[]) {
    lld N;      scanf("%lld", &N);
    dfs(0LL);
    sort(V.begin(), V.end());

    //      start node is "0"
    queue<lld> Q;
    Q.push(0LL);
    M.insert(make_pair(0LL, -1LL));

    while (!Q.empty()) {
        lld current = Q.front();
        Q.pop();
        if(current==N)
            break;
        if(current>N)   
            continue;

        //      Note. V[0]=0.
        //      So, I consider from index 1.
        for (int i = 1; i < V.size(); i++) {
            lld next = current + V[i];
            if (0LL <= next && next <= MAXN) {
                if (M.find(next) == M.end()) {
                    M.insert(make_pair(next, current));
                    Q.push(next);
                }
            }
        }
    }

    if (M.find((lld)N) == M.end()) {
        printf("-1\n");
    }
    else {
        reconstruct((lld)N);
    }

    return 0;
}

Could you give me some hint?

Answer 1

Note that all lucky numbers can be written as A * 4 + B * 7 with some restrictions on A and B, so there is no need to generate all lucky numbers. Start by solving N = A * 4 + B * 7 for A and B. After you have A and B, find the lucky numbers. For example if A = 12 = 1 + 11 and B = 20 = 10 + 10 possible combination of lucky numbers is: 4, 44, 77, 77.