Find Three Consecutive Integers That Sum to a Given Number - Complete Solution Guide

Find Three Consecutive Integers That Sum to a Given Number is LeetCode problem 2177, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 1

Detailed Explanation

The problem asks us to find three consecutive integers that sum up to a given integer `num`. If such three integers exist, we should return them in a sorted array. If not, we should return an empty array. The input `num` is a non-negative integer within the range [0, 10^15].

Solution Approach

The solution checks if the input number `num` is divisible by 3. If it is, it calculates the middle number `x` by dividing `num` by 3. Then, it constructs an array containing the three consecutive integers `x-1`, `x`, and `x+1` and returns it. If `num` is not divisible by 3, it returns an empty array.

Step-by-Step Algorithm

1. Step 1: Check if `num` is divisible by 3 (i.e., `num % 3 == 0`).
2. Step 2: If `num % 3 != 0`, return an empty array.
3. Step 3: If `num % 3 == 0`, calculate `x = num // 3` (integer division).
4. Step 4: Create an array containing `x - 1`, `x`, and `x + 1`.
5. Step 5: Return the array.

Key Insights

• Insight 1: If three consecutive integers `x-1`, `x`, and `x+1` sum to `num`, then `(x-1) + x + (x+1) = 3x = num`. This means `x = num / 3`. Thus, `num` must be divisible by 3 for a solution to exist.
• Insight 2: If `num` is divisible by 3, then the middle integer `x` is simply `num // 3`, and the other two integers are `x - 1` and `x + 1`.
• Insight 3: The constraints on 'num' (up to 10^15) require the use of long data types in Java and C++ to avoid integer overflow during division and other calculations.

Complexity Analysis

Time Complexity: O(1)

Space Complexity: O(1)

Topics

This problem involves: Math, Simulation.

Companies

Asked at: FPT.