Find Three Consecutive Integers That Sum to a Given Number
MedPrompt
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 <= 1015
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward, yet inefficient, way to solve this problem is to search for the three consecutive integers. We can iterate through a wide range of numbers, treating each one as the potential middle number of our sequence. For each number x, we check if (x-1) + x + (x+1) equals num.
Algorithm
- Iterate through a range of possible integer values for
x, the middle number. - For each
x, calculate the sum3 * x. - If
3 * xequalsnum, then we have found our sequence:[x-1, x, x+1]. Return this array. - If the loop completes without finding a match, return an empty array.
Walkthrough
This approach involves iterating through possible values for the middle integer, x, of the three consecutive integers. The sum of these integers is (x-1) + x + (x+1), which simplifies to 3x. The goal is to find an integer x such that 3x = num.
Because the constraints on num are up to 10^15, a linear search for x is not feasible as it would take far too long to execute. This method is purely for conceptual understanding and would fail in practice due to a "Time Limit Exceeded" error.
class Solution { // This is a conceptual illustration of a brute-force approach. // It is not a practical solution for the given constraints and will time out. public long[] sumOfThree(long num) { // The middle number 'x' will be around num / 3. // A brute-force search would have to check a wide range around this value. // For example, from 0 up to num, which is too slow. long limit = num; // A very loose upper bound for (long x = 0; x <= limit; x++) { // Using long to prevent overflow for 3*x if (3 * x == num) { return new long[]{x - 1, x, x + 1}; } } // This loop doesn't handle negative numbers, which might be required // (e.g., for num=0, the answer is [-1, 0, 1]). A complete brute force // would need to check negative values as well, making it even slower. return new long[]{}; }}Complexity
Time
O(N), where N is the size of the search space. For a number `num` up to `10^15`, this is prohibitively slow.
Space
O(1), as we only use a few variables to store the current number and sum. This does not include the space for the output array.
Trade-offs
Pros
Conceptually simple and easy to understand.
Cons
Extremely inefficient and will result in a 'Time Limit Exceeded' error for the given constraints.
Does not easily handle cases requiring negative integers without expanding the search range significantly.
Solutions
Solution
class Solution {public long[] sumOfThree(long num) { if (num % 3 != 0) { return new long[]{}; } long x = num / 3; return new long[]{x - 1, x, x + 1}; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.