#2177

Medium

LeetCode Problem Workspace

Find Three Consecutive Integers That Sum to a Given Number

Given a number, find three consecutive integers that sum to it, or return an empty array if no such integers exist.

Problem Statement

You are given an integer num, and you need to return an array of three consecutive integers that sum to num. If no such integers exist, return an empty array.

For example, if num = 33, the three integers that sum to it are [10, 11, 12], but if num = 4, no three consecutive integers sum to it, so you return an empty array.

Examples

Example 1

Input: num = 33

Output: [10,11,12]

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: []

There is no way to express 4 as the sum of 3 consecutive integers.

Constraints

0 <= num <= 1015

Solution Approach

Mathematical Insight

The sum of three consecutive integers can be expressed as x-1, x, x+1. Therefore, if a solution exists, we can calculate the middle integer x directly by solving the equation (num / 3). If x is an integer, the three integers are x-1, x, x+1.

Simulation of Solution

We simulate the potential consecutive integers using the formula for three consecutive numbers and check if their sum equals the given num. If no valid combination is found, return an empty array.

Edge Case Handling

If the number is too small or too large, or if it cannot be split into three consecutive integers, ensure that the algorithm handles such cases and returns an empty array when necessary.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(1) as the solution involves basic mathematical operations without any loops or recursion. The space complexity is also O(1) as we are only returning a fixed-size array (of size 3 or 0).

What Interviewers Usually Probe

Understand if the candidate can recognize and leverage patterns in number theory.
Evaluate the candidate's ability to quickly derive a mathematical approach and apply it in simulation.
Check if the candidate can handle edge cases, such as small or large values of num.

Common Pitfalls or Variants

Common pitfalls

Failing to recognize the mathematical relationship between three consecutive numbers and their sum.
Overcomplicating the solution by trying unnecessary loops or searches.
Not correctly handling edge cases, like when num is too small or large for a valid solution.

Follow-up variants

Generalizing the problem to find n consecutive integers that sum to a given number.
Changing the number of integers to sum (e.g., four or five consecutive integers).
Adding constraints such as finding consecutive prime numbers that sum to a given number.

FAQ

How do I approach finding consecutive integers that sum to a number?

Start by recognizing that three consecutive integers can be expressed as x-1, x, x+1. If the sum is valid, x can be calculated directly.

What is the time complexity of this problem?

The time complexity is O(1) as the solution involves only basic mathematical calculations without loops.

What happens if no three consecutive integers sum to the number?

If no solution exists, return an empty array, indicating that it's not possible to express the number as the sum of three consecutive integers.

Can the GhostInterview platform help with similar mathematical problems?

Yes, GhostInterview can help by breaking down similar problems and applying mathematical patterns to find solutions.

What if the number is too large for consecutive integers to sum?

If the number is too large or cannot be split into three consecutive integers, the solution will return an empty array.

terminal

Solution

Solution 1: Mathematics

Assume the three consecutive integers are $x-1$, $x$, and $x+1$. Their sum is $3x$, so $\textit{num}$ must be a multiple of $3$. If $\textit{num}$ is not a multiple of $3$, it cannot be represented as the sum of three consecutive integers, and we return an empty array. Otherwise, let $x = \frac{\textit{num}}{3}$, then $x-1$, $x$, and $x+1$ are the three consecutive integers whose sum is $\textit{num}$.

1

2

3

4

class Solution:
    def sumOfThree(self, num: int) -> List[int]:
        x, mod = divmod(num, 3)
        return [] if mod else [x - 1, x, x + 1]

Continue Practicing

#2180 count integers with even digit sum #2169 count operations to obtain zero #2221 find triangular sum of an array