 # IT1 - Editorial

Author: Anita Acha George
Tester: Alex Mathew
Editorialist: Alex Mathew

EASY

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;
``````

}

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.