Find Three Consecutive Integers That Sum to a Given Number

MEDIUM

Description

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¹⁵

Approaches

Checkout 2 different approaches to solve Find Three Consecutive Integers That Sum to a Given Number. Click on different approaches to view the approach and algorithm in detail.

Brute Force Search

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 sum 3 * x.
If 3 * x equals num, 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.

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 Analysis

Time Complexity: O(N), where N is the size of the search space. For a number `num` up to `10^15`, this is prohibitively slow.Space Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Find Three Consecutive Integers That Sum to a Given Number. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Find Three Consecutive Integers That Sum to a Given Number

Patterns:

Math

Companies:

FPT |