### PROBLEM LINK:

**Author:** Anita Acha George

**Tester:** Alex Mathew

**Editorialist:** Alex Mathew

### DIFFICULTY:

EASY

### PREREQUISITES:

OBSERVATION

### PROBLEM:

Hari loves to play with numbers. He finds that the numbers 4 and 7 are lucky for him. So he also considers positive integer numbers whose decimal representation contains only the lucky digits 4 and 7 as lucky. For example, numbers 47, 744, 4 are lucky for him and 5, 17, 467 are not.

Hari calls a number almost lucky if it could be evenly divided by some lucky number. Help him find out if the given number n is almost lucky.

### QUICK EXPLANATION:

First find all lucky numbers by finding if number contains 4 and/or 7. Then for the given range divide all numbers by lucky numbers and check perfect division.

### EXPLANATION:

Find a lucky number. To do this we need to divide the number by 10 until the number is not equal to 0 and check if the reminder is equal to 4 or 7 i.e. it contains only the digits 4 and 7. If it’s not then we can confirm that the number is not lucky. Otherwise it is a lucky number. This has a complexity of O(n).

bool lucky(int n)

{

```
while (n != 0)
{
if (n % 10 != 4 AND n % 10 != 7)
{
return false;
}
n/=10;
}
return true;
```

}

Subtask 2

Find an almost lucky number. For this we need to check if the number is divisible by a lucky number. For that we need to traverse from 2 to the number to find all the factors of the number and then we need to see if the factor is a lucky number or not.

bool almost_lucky(int n)

{

```
if (lucky(n))
{
return true;
}
for (int i = 2; i * i <= n; ++i)
{
if (n % i == 0 AND (lucky(i) || lucky(n / i)))
{
return true;
}
}
```

}

This code runs with a complexity of O(n)

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.