Codeforces 122A Lucky Division Solution in C (Generating Lucky Numbers)

Lucky Division (122A) is a small number theory problem, and it is a good place to practice one habit: when the input is small, generate everything and check it. It also has a trap. If you list the lucky numbers by hand, it is easy to miss some, and an earlier version of this very post did exactly that.

The problem in short

A positive integer is lucky if its decimal digits are only 4s and 7s (for example 4, 47, 744). A number is almost lucky if it is divisible by some lucky number. Given n (1 ≤ n ≤ 1000), print YES if it is almost lucky, otherwise NO.

Full statement: Codeforces 122A – Lucky Division.

Which lucky numbers do we need?

A divisor of n can never be larger than n, and n ≤ 1000. So we need every lucky number up to 1000. With 1 digit there are 2 (4, 7), with 2 digits there are 4 (44, 47, 74, 77) and with 3 digits there are 8, giving 14 in total:

4 7 44 47 74 77 444 447 474 477 744 747 774 777

The old version of this post skipped 77, 744, 747, 774 and 777. Some of those are harmless to skip, since 77 and 777 are multiples of 7 and 744 is a multiple of 4. But 747 and 774 are not divisible by any smaller lucky number, so the old code wrongly printed NO for them. That is why it is safer to list the full set than to reason about which ones you can drop.

Approach

Loop over the 14 lucky numbers. If any of them divides n exactly, print YES. If none do, print NO.

Examples

• n = 47: 47 is itself lucky, so it divides itself → YES.
• n = 16: 16 is divisible by 4 → YES.
• n = 78: 78 = 2 × 3 × 13. None of the 14 lucky numbers divide it → NO.

Solution in C

#include <stdio.h>

/* All lucky numbers that are <= 1000 (the problem's limit). */
int lucky[] = {4, 7, 44, 47, 74, 77, 444, 447, 474, 477, 744, 747, 774, 777};

int main(void) {
    int n;
    scanf("%d", &n);

    int count = sizeof(lucky) / sizeof(lucky[0]);
    for (int i = 0; i < count; i++) {
        if (n % lucky[i] == 0) {
            printf("YES\n");
            return 0;
        }
    }
    printf("NO\n");
    return 0;
}

Going further: generating the list

If the limit were 10⁹ instead of 1000, you would not want to type the list. You can generate lucky numbers recursively: start from 0, and from any number x produce 10x + 4 and 10x + 7, stopping once the value passes the limit. There are only 2 + 4 + … + 2⁹ = 1022 lucky numbers below 10⁹, so even that is tiny.

Complexity

14 divisions per input: O(1) time and memory.

Practice next

For another “check a small fixed set” idea, see 282A Bit++. For a math shortcut problem, try 4A Watermelon.