IT1 - Editorial

PROBLEM LINK:

Practise
Contest

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.