Starting a new series here. When applying to a Software Engineer or Data Engineer role it's a standard to have a live or asynchronous coding interview. Most of the challenges you will need to crack don't reflect the day to day work you will do but are a great way to assess you problem solving skills and coding style. As I believe most of these exercises are great puzzles and fun to solve I will start bringing my own version of some of these. Who knows if one of these days you won't be asked to solve it. This time I am bringing you the classic divisible by 8 problem.
In this exercise you are asked to check if a long number can de divisible without using the division remainder of a number (Eg: IF number % 8 == 0 THEN True ELSE False ) and if by permuting any number you can obtain a number that is divisible by 8.
Looking at the problem we can spot a few goals:
- Find an algorithm that check check the divisibility by 8 without doing an operation with the whole number but only a part of it.
- Design a permutation algorithm that can check if we change the position of a few digits in a number we can obtain a number that is divisible by 8 (Eg: 242 is not divisible by 8 BUT 224 is – We changed the position of the 4 with the last 2)
If you still remember from you math classes there are a few divisible rules that can be used:
- Divisible by 2: Any even number can be divided by 2. We only need to look at the last digit.
- Divisible by 3: A number is divisible by 3 if the sum of its digits is divisible by 3. We can sum all digits and assess the resulting number.
- Divisible by 4: A number is divisible by 4 if the number’s last two digits are divisible by 4. We only look at the last two digits of a long number.
- Divisible by 5: A number is divisible by 5 if its last digit is a 0 or 5. We only need to look at the last digit.
- Divisible by 6: A number is divisible by 6 if it is even and if the sum of its digits is divisible by 3. We need to look at last digit and the sum of all digits.
- Divisible by 8: A number passes the test for 8 if the last three digits form a number is divisible 8. We can look only at the last three digits of a number.
Now that we have a rule, let’s start cracking this problem. Although we cannot use the division remainder with the whole long number, we still need it to assess the last 3 digits, so let’s start by creating a function to assess that.
# Check if number is divisible by 8
def check_divisible(number):
if int(number) % 8 == 0:
return True
return False
The next step is building a function that looks at the last three digits of a number and that using our check_divisible() function checks if they are divisible by 8.
def check_divisible_by_8(number):
# Get last 3 digits
last_three_digits = str(number)[-3:]
# Call previous function and return result
return check_divisible(last_three_digits)
This would be ok if we didn’t have the permutation request as well namely if by changing one digit of place we can obtain a number that is divisible by 8. For this I have decided to use a dictionary that will store all my digit frequencies so that I can compare against all the three digits possibilities that are divisible by 8 and check if my frequencies are enough to obtain that permutation. If positive than it means I can perform a permutation that results in a long number divisible by 8.
Eg: 15242 is not divisible by 8, let’s apply our algorithm:
- Get frequencies = {1: 1, 5:1, 2:2, 4:1} This means we observed 1 once, 5 once, 2 twice and 4 once.
- Now, if we compare this with the 3 digits divisible by 8 224 we can see that the frequencies in this number are {2:2, 4:1} which means we need two 2 and one 4 to exist in the original number to be able to get this at the end of the long number
- Conclusion: Because we have in fact two 2s and one 4 in the original number, we could change it from 15242 to 15224 and that is divisible by 8.
Now let’s write the code for that. First we need a function that given a number as input, returns a dictionary with the digits frequencies.
def get_number_frequency(number):
unique_numbers = {}
for nb in str(number):
if nb in unique_numbers:
unique_numbers[nb] +=1
else:
unique_numbers[nb] = 1
return unique_numbers
Now we need a function to apply the frequencies comparison logic we discussed before.
# Complexity 2: check if any permutation is divisible by 8
def check_permutations(number):
freq_table = get_number_frequency(number)
# check from possible permutations for 3 digits
for i in range(0,1000):
# format number to have always 3 digits
perm = "{:03d}".format(i)
# Only check this set of 3 number if divisible by 8
if check_divisible(int(perm)):
# Get frequency of numbers in this possible divisible by 8
perm_table = get_number_frequency(perm)
#check if permutation can be achieved
is_possible = True
for f in perm_table:
if f not in freq_table:
is_possible = False
break
if perm_table[f] > freq_table[f]:
is_possible = False
break
# Check if this permutation is possible
if is_possible == True:
# Because conditions did not fail, this permutation is possible. No need to continue the cycle, just return True
print("This permutation is possible {}".format(perm))
return True
else:
# Not divisible by 8
continue
# this permutation is not possible
return False
# Now lets test it
long_number = 757577575757754884848484
print(check_permutations(long_number))
The result you will obtain is:
This permutation is possible 448 True
This result means that although 757577575757754884848484 is not divisible by 8, we can change the digits so that we obtain 448 at the end of the number, namely 757577575757754884848448 which is divisible by 8.
Full code available bellow
"""
Created on Wed Mar 10
@author: ruimachado
Goal: Check if large number is divisible by 8
Rules:
1. A number is divisible by 8 if its last three digits are divisible by 8
2. Check if any permutation would make the number divisible by 8
Solution:
1. Get all number frequencies
2. Get all possibilities for 3 digits
3. Compare 2 with 1 and check if frequencies allow the possibility
4. In case you have a positive case, return true
"""
# Check if number is divisible by 8
def check_divisible(number):
if int(number) % 8 == 0:
return True
return False
def check_divisible_by_8(number):
# Get last 3 digits
last_three_digits = str(number)[-3:]
# Call previous function and return result
return check_divisible(last_three_digits)
def get_number_frequency(number):
unique_numbers = {}
for nb in str(number):
if nb in unique_numbers:
unique_numbers[nb] +=1
else:
unique_numbers[nb] = 1
return unique_numbers
# Complexity 2: check if any permutation is divisible by 8
def check_permutations(number):
freq_table = get_number_frequency(number)
# check from possible permutations for 3 digits
for i in range(0,1000):
# format number to have always 3 digits
perm = "{:03d}".format(i)
# Only check this set of 3 number if divisible by 8
if check_divisible(int(perm)):
# Get frequency of numbers in this possible divisible by 8
perm_table = get_number_frequency(perm)
#check if permutation can be achieve by input number frequencies
is_possible = True
for f in perm_table:
if f not in freq_table:
is_possible = False
break
if perm_table[f] > freq_table[f]:
is_possible = False
break
# Check if this permutation is possible
if is_possible == True:
# Because conditions did not fail, this permutation is possible
print("This permutation is possible {}".format(perm))
return True
else:
# Not divisible by 8
continue
# this permutation is not possible
return False
long_number = 757577575757754884848484
print(check_permutations(long_number))
And that’s it. In case you want me to crack some exercises send them in.
Happy to make a post about it
Datavoid 