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.
A much more efficient solution comes from a simple algebraic insight. Let the three consecutive integers be x-1, x, and x+1. Their sum is (x-1) + x + (x+1) = 3x. This means that for a number num to be a sum of three consecutive integers, it must be a multiple of 3.
Algorithm
- Check if
numis divisible by 3 using the modulo operator (num % 3). - If
numis not divisible by 3, return an empty array. - If
numis divisible by 3, calculate the middle integerx = num / 3. - Construct and return the result array
[x-1, x, x+1].
Walkthrough
Based on the mathematical property that the sum of three consecutive integers is always three times the middle integer (3x), we can directly determine if a solution exists and what it is. This avoids any iteration or searching.
If the sum of three consecutive integers (x-1), x, (x+1) is num, then 3x = num. For x to be an integer, num must be perfectly divisible by 3. We can use this condition to solve the problem directly.
class Solution { public long[] sumOfThree(long num) { // Let the three consecutive integers be x-1, x, and x+1. // Their sum is (x-1) + x + (x+1) = 3x. // So, we need to solve for x in the equation 3x = num. // This means x = num / 3. // For x to be an integer, num must be divisible by 3. if (num % 3 == 0) { // If num is divisible by 3, a solution exists. long x = num / 3; // The three consecutive integers are x-1, x, and x+1. return new long[]{x - 1, x, x + 1}; } else { // If num is not divisible by 3, no integer solution for x exists. return new long[]{}; } }}Complexity
Time
O(1). The solution involves a single modulo and a division, which are constant-time operations, regardless of the input size.
Space
O(1), as only a few variables are needed. This does not include the space for the output array.
Trade-offs
Pros
Optimal and extremely fast.
Works for all valid inputs within the constraints, including those requiring negative integers.
Simple and elegant implementation.
Cons
Requires recognizing the underlying mathematical pattern.
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}; }}/** * @param {number} num * @return {number[]} */ var sumOfThree = function ( num,) { if (num % 3) { return []; } const x = Math.floor(num / 3); return [x - 1, x, x + 1];};class Solution {public: vector<long long> sumOfThree(long long num) { if (num % 3) { return {}; } long long x = num / 3; return {x - 1, x, x + 1}; }};class Solution: def sumOfThree(self, num: int) -> List[int]: x, mod = divmod(num, 3) return [] if mod else [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.