Teaching Kids Programming – Multiples of 3 and 7

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a positive integer n, determine whether you can make n by summing up some non-negative multiple of 3 and some non-negative multiple of 7.

Constraints
n < 2 ** 31
Example 1
Input
n = 13
Output
True
Explanation
We can get 13 with 1 * 7 + 2 * 3.

Example 2
Input
n = 9
Output
True
Explanation
We can get 9 with 3 3s.

Recursive Algorithm to Check Multiples of 3 and 7

Recursively checking if n-3 or n-7 can be multiples of 3 and 7 – and we can cache the intermediate results using @cache. This is kinda Top Down Dynamic Programming Algorithm that is implemented with Recursion plus Memoization aka caching.

1
2
3
4
5
6
7
8

class Solution:
    @cache
    def multiplesOfThreeAndSeven(self, n):
        if n < 0:
            return False
        if n % 3 == 0 or n % 7 == 0:
            return True
        return self.solve(n - 3) or self.solve(n - 7)

class Solution:
    @cache
    def multiplesOfThreeAndSeven(self, n):
        if n < 0:
            return False
        if n % 3 == 0 or n % 7 == 0:
            return True
        return self.solve(n - 3) or self.solve(n - 7)

Time complexity O(N) and space complexity O(N).

Iterative Checking Multiples of 3 and 7

We can bruteforce checking all numbers n-3i if divisble by seven.

1
2
3
4
5
6

class Solution:
    def multiplesOfThreeAndSeven(self, n):
        for i in range(n//3+1):
            if (n - i * 3) % 7 == 0:
                return True
        return False

class Solution:
    def multiplesOfThreeAndSeven(self, n):
        for i in range(n//3+1):
            if (n - i * 3) % 7 == 0:
                return True
        return False

Simplified version of one-liner:

1
2
3

class Solution:
    def multiplesOfThreeAndSeven(self, n):
        return any((n-i*3)%7==0 for i in range(n//3+1))

class Solution:
    def multiplesOfThreeAndSeven(self, n):
        return any((n-i*3)%7==0 for i in range(n//3+1))

Time complexity O(N), space complexity O(1).

Chicken McNugget Theorem

There is a Chicken McNugget Theorem also known as Postage Stamp Problem or Frobenius Coin Problem. Given any two relatively prime numbers a, b the greatest N that cannot be represented as ax + by = N is (a*b) – a – b (where x and y both non-negative integers).

For this problem, a = 3 and b = 7 and they are relatively prime. So we know for any number bigger than 11 (3×7-3-7), the answer is true.

And for other numbers less than 11, we can check them on pen and paper.

1
2
3
4
5

class Solution:
    def multiplesOfThreeAndSeven(self, n):
        if n == 8:
            return False;
        return (n > 11 or (n >= 6 and n <= 10) or n == 3 or n == 7)

class Solution:
    def multiplesOfThreeAndSeven(self, n):
        if n == 8:
            return False;
        return (n > 11 or (n >= 6 and n <= 10) or n == 3 or n == 7)

Time complexity O(1), space complexity O(1).

–EOF (The Ultimate Computing & Technology Blog) —