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.