LeetCode Problem 2177

Difficulty: 🟡 Medium
Topics: Math, Simulation

Solution

LeetCode 2177 - Find Three Consecutive Integers That Sum to a Given Number

Problem Understanding

This problem asks us to determine whether a given integer num can be represented as the sum of three consecutive integers. If such a representation exists, we must return those three integers in sorted order. Otherwise, we return an empty array.

Three consecutive integers always follow the pattern:

x, x + 1, x + 2

Their sum is:

x + (x + 1) + (x + 2) = 3x + 3

This means the total sum must always be divisible by 3.

The input consists of a single integer num, and the output is either:

• A list containing three consecutive integers whose sum equals num
• An empty list if no such integers exist

The constraints are important:

• 0 <= num <= 10^15

The upper bound is extremely large, so any algorithm that iterates through many possible values would be inefficient. We need a mathematical observation that allows us to solve the problem in constant time.

Several edge cases are important:

• Small values such as 0, 1, or 2
• Numbers not divisible by 3
• Very large numbers near 10^15
• Cases where the consecutive integers include 0

The problem guarantees that num is non-negative, so we do not need to handle negative inputs.

Approaches

Brute Force Approach

A straightforward approach is to try every possible starting integer x and check whether:

x + (x + 1) + (x + 2) == num

If the equality holds, we return [x, x + 1, x + 2].

This approach is correct because it exhaustively checks every possible group of three consecutive integers. However, it is inefficient because the search space grows with num. Since num can be as large as 10^15, iterating through candidates is completely impractical.

Optimal Mathematical Approach

The key insight comes from algebra.

Suppose the three consecutive integers are:

x - 1, x, x + 1

Their sum is:

(x - 1) + x + (x + 1) = 3x

This immediately tells us that:

• A valid solution exists if and only if num is divisible by 3
• The middle number is num // 3

Once we know the middle number, the answer becomes:

[num // 3 - 1, num // 3, num // 3 + 1]

This eliminates all searching and gives an O(1) solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(num)	O(1)	Checks every possible starting value
Optimal	O(1)	O(1)	Uses divisibility property of consecutive sums

Algorithm Walkthrough

1. Check whether num is divisible by 3.

Three consecutive integers always sum to a multiple of 3. If num % 3 != 0, no valid solution exists, so we immediately return an empty array. 2. Compute the middle integer.

If num is divisible by 3, let:

middle = num // 3

The three integers must then be:

middle - 1
middle
middle + 1

3. Return the result array.

Construct and return:

[middle - 1, middle, middle + 1]

Why it works

The correctness comes directly from the structure of consecutive integers. Any three consecutive integers can always be written as:

x - 1, x, x + 1

Their sum simplifies to:

3x

Therefore, a valid solution exists exactly when num is divisible by 3. When it is divisible, x = num / 3, which uniquely determines the three integers.

Python Solution

from typing import List

class Solution:
    def sumOfThree(self, num: int) -> List[int]:
        if num % 3 != 0:
            return []

        middle = num // 3

        return [middle - 1, middle, middle + 1]

The implementation begins by checking divisibility by 3. If the remainder is non-zero, the function immediately returns an empty list because no valid triple can exist.

If the number is divisible by 3, the code computes the middle integer using integer division. The surrounding consecutive integers are then generated by subtracting and adding 1.

The solution is concise because the mathematical relationship completely determines the answer.

Go Solution

func sumOfThree(num int64) []int64 {
    if num%3 != 0 {
        return []int64{}
    }

    middle := num / 3

    return []int64{middle - 1, middle, middle + 1}
}

The Go implementation follows the same mathematical reasoning as the Python solution.

One important Go-specific detail is the use of int64, because the constraint allows values up to 10^15. Using regular int could cause overflow on some systems. The function returns an empty slice when no solution exists.

Worked Examples

Example 1

Input: num = 33

First, check divisibility:

Expression	Value
33 % 3	0

Since the remainder is 0, a solution exists.

Compute the middle value:

Variable	Value
middle	33 // 3 = 11

Construct the result:

Integer	Value
middle - 1	10
middle	11
middle + 1	12

Final answer:

[10, 11, 12]

Verification:

10 + 11 + 12 = 33

Example 2

Input: num = 4

Check divisibility:

Expression	Value
4 % 3	1

Since the remainder is not 0, no valid triple exists.

Final answer:

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a few arithmetic operations are performed
Space	O(1)	The output size is fixed at at most three integers

The algorithm does not depend on the magnitude of num. Even for extremely large values such as 10^15, the same constant number of operations is performed.

Test Cases

from typing import List

class Solution:
    def sumOfThree(self, num: int) -> List[int]:
        if num % 3 != 0:
            return []

        middle = num // 3
        return [middle - 1, middle, middle + 1]

solution = Solution()

assert solution.sumOfThree(33) == [10, 11, 12]  # provided example
assert solution.sumOfThree(4) == []  # not divisible by 3
assert solution.sumOfThree(0) == [-1, 0, 1]  # smallest divisible case
assert solution.sumOfThree(3) == [0, 1, 2]  # simple valid case
assert solution.sumOfThree(6) == [1, 2, 3]  # another small valid case
assert solution.sumOfThree(1) == []  # too small and not divisible
assert solution.sumOfThree(2) == []  # not divisible by 3
assert solution.sumOfThree(999999999999999) == [
    333333333333332,
    333333333333333,
    333333333333334
]  # very large divisible value
assert solution.sumOfThree(1000000000000000) == []  # very large non-divisible value

Test Case Summary

Test	Why
33	Valid example from the prompt
4	Non-divisible case
0	Edge case involving negative and zero values
3	Smallest positive divisible value
6	Standard valid sequence
1	Small invalid value
2	Another invalid small value
999999999999999	Stress test with huge divisible number
1000000000000000	Stress test with huge non-divisible number

Edge Cases

Input Equal to Zero

When num = 0, some implementations may incorrectly assume that all returned integers must be positive. However, the problem only requires consecutive integers, not positive integers.

The correct sequence is:

[-1, 0, 1]

The implementation handles this naturally because integer division still works correctly.

Numbers Not Divisible by Three

A common bug is attempting to construct a sequence even when num is not divisible by 3. For example:

num = 4

No three consecutive integers can sum to 4.

The implementation avoids this issue by immediately checking:

if num % 3 != 0:
    return []

Very Large Numbers

Since num can be as large as 10^15, iterative approaches become infeasible. A brute force solution could potentially require trillions of operations.

The mathematical solution performs only constant-time arithmetic operations, so it scales perfectly even for the maximum constraint. The Go solution additionally uses int64 to safely store large values without overflow.