# Find Three Consecutive Integers That Sum to a Given Number
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-three-consecutive-integers-that-sum-to-a-given-number)
Canonical: https://scaleengineer.com/dsa/problems/find-three-consecutive-integers-that-sum-to-a-given-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [FPT](https://scaleengineer.com/companies/fpt)
---
## Problem
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
## 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`.
**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.
**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.
### Explanation
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.

```java
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[]{};
    }
}
```
### 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.

## Direct Calculation using Mathematical Property
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.
**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.
**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.
### Explanation
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.

```java
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[]{};
        }
    }
}
```
### Algorithm
*   Check if `num` is divisible by 3 using the modulo operator (`num % 3`).
*   If `num` is not divisible by 3, return an empty array.
*   If `num` is divisible by 3, calculate the middle integer `x = num / 3`.
*   Construct and return the result array `[x-1, x, x+1]`.

# Solutions
### Java

```java
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};
  }
}

```

### JavaScript

```javascript
/** * @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];
};

```

### CPP

```cpp
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};
  }
};

```

### Python

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

```