Teaching Kids Programming – Find Three Consecutive Integers That Sum to a Given Number

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given an integer num, return three consecutive integers (as a sorted array) that sum to num. If num cannot be expressed as the sum of three consecutive integers, return an empty array.

Example 1:
Input: num = 33
Output: [10,11,12]
Explanation: 33 can be expressed as 10 + 11 + 12 = 33.
10, 11, 12 are 3 consecutive integers, so we return [10, 11, 12].

Example 2:
Input: num = 4
Output: []
Explanation: There is no way to express 4 as the sum of 3 consecutive integers.

Constraints:
0 <= num <= 10^15

Algorithm to Find Three Consecutive Integers That Sum to a Given Number

We can bruteforce the first number from -1 up to one third:

1
2
3
4
5
6
7

class Solution:
    def sumOfThree(self, num: int) -> List[int]:       
        # O(N)
        for first in range(-1, num // 3 + 1):
            if first + first + 1 + first + 2 == num:
                return [first, first + 1, first + 2]
        return []

class Solution:
    def sumOfThree(self, num: int) -> List[int]:       
        # O(N)
        for first in range(-1, num // 3 + 1):
            if first + first + 1 + first + 2 == num:
                return [first, first + 1, first + 2]
        return []

Time complexity is O(N).

If the second number is x, the first number is x – 1, and the third number is x + 1, thus so we can work out the middle number of three consecutive integers easily by math.

1
2
3
4
5
6
7

class Solution:
    def sumOfThree(self, num: int) -> List[int]:       
        # O(1)
        if num % 3 != 0:
            return []
        mid = num // 3
        return [mid - 1, mid, mid + 1]

class Solution:
    def sumOfThree(self, num: int) -> List[int]:       
        # O(1)
        if num % 3 != 0:
            return []
        mid = num // 3
        return [mid - 1, mid, mid + 1]

Time complexity is O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —