2177. Find Three Consecutive Integers That Sum to a Given Number

MediumMathSimulation

Problem Description

The problem requires writing a function that takes an integer num as an input and outputs three consecutive integers whose sum equals num. If no such three consecutive numbers exist, the function should return an empty array. Consecutive integers are numbers that follow each other without any gaps; for example, 4, 5, 6 are consecutive integers.

Intuition

To solve this problem, we exploit the property that the sum of any three consecutive integers is always divisible by 3. To understand why, consider any three consecutive integers n - 1, n, and n + 1. Their sum is (n - 1) + n + (n + 1), which simplifies to 3n. Because the sum is simply 3n, it's clear that any three consecutive integers must sum up to a multiple of 3.

Knowing this, we can check whether our given integer num is divisible by 3, to determine if it's possible to find such three numbers. We do this by using the divmod function which takes two numbers and returns a pair (tuple) consisting of their quotient and remainder.

If num is divisible by 3 (remainder is 0), we know that num can be expressed as the sum of three consecutive integers. We can find the middle integer by dividing num by 3. Let's denote this middle integer as x. Then, the three consecutive numbers would be x - 1, x, and x + 1.

If num is not divisible by 3 (remainder is not 0), we return an empty array, since there is no set of three consecutive integers that sum up to num.

The provided Python solution uses the approach described above. It declares a class Solution with a method sumOfThree that accepts an integer num and returns a list of integers. The method calculates the quotient x and the remainder mod when num is divided by 3. It then checks if the remainder mod is zero; if so, it returns a list containing x - 1, x, and x + 1. If the remainder is not zero, it means that num cannot be expressed as the sum of three consecutive numbers, and the method returns an empty list.

Learn more about Math patterns.

Solution Approach

The solution to this problem uses a straightforward algorithm that incorporates basic arithmetic operations and conditional logic. It's a single pass approach without the need for any complex data structures. Here's an in-depth walk-through of the solution's implementation:

Division and Modulus Operations: The solution employs the divmod function which takes two arguments and returns a tuple containing the quotient and remainder of the division. In this case, divmod(num, 3) gives us the quotient x and the remainder mod. For example, if num is 6, calling divmod(6, 3) would return (2, 0) since 6 divided by 3 is 2 with a remainder of 0.
Conditional Check: After getting the quotient and the remainder, we check if the mod is zero. This is a crucial step because if the remainder is zero, num is divisible by 3 and we can express it as a sum of three consecutive integers according to the property mentioned earlier. Otherwise, it cannot be expressed as such and we return an empty list.
Calculating the Consecutive Integers: If the remainder is zero, we find the middle integer x by simply using the quotient. The three consecutive integers will be (x - 1, x, x + 1). For instance, if num is 27, divmod(27, 3) returns (9, 0). The consecutive integers would then be (8, 9, 10).
Returning the Result: In the end, the solution either returns the list of the three consecutive integers if the remainder is zero or an empty list if it's not. This is done using a simple ternary conditional expression in Python: [] if mod else [x - 1, x, x + 1]. This line checks if mod is True (which in Python means any number other than 0). If it's True (non-zero remainder), it returns []. If mod is False (zero remainder), it returns [x - 1, x, x + 1].

The solution is efficient and runs in constant time O(1) because it always performs a fixed number of operations regardless of the input size. The space complexity is also O(1) since it only stores a few variables and potentially returns an array with three integers at most.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's work through a small example to illustrate the solution approach. Imagine the function sumOfThree is called with an input number num = 15. Here's a step-by-step breakdown of how the function will process this input:

Division and Modulus Operations: The function starts by using the divmod function to divide num by 3. We call divmod(15, 3) which returns (5, 0) because 15 divided by 3 is exactly 5 with no remainder.
Conditional Check: The function then checks whether the remainder mod is zero. In this case, since mod is 0 (divmod returned (5, 0)), our input number is divisible by 3.
Calculating the Consecutive Integers: Knowing that 15 is divisible by 3, the function determines that it can be expressed as the sum of three consecutive integers. It uses the quotient (x = 5) to find these numbers. They are the integers (x - 1), x, and (x + 1), thus (4, 5, 6).
Returning the Result: Since the remainder was zero, the function returns the list [4, 5, 6]. These numbers are indeed consecutive, and their sum is 15, meeting the original problem's requirements.

Hence, for num = 15, the sumOfThree function yields [4, 5, 6].

Let us consider a scenario where sumOfThree is called with num = 16:

Division and Modulus Operations: By calling divmod(16, 3), the function gets (5, 1), meaning the quotient is 5 and the remainder is 1.
Conditional Check: Since the remainder mod is not zero, we conclude that 16 cannot be divided evenly by 3.
Calculating the Consecutive Integers: There is no need for this step because we've already determined that the number cannot be divided into three consecutive integers.
Returning the Result: The function returns an empty list [], indicating that there is no sequence of three consecutive numbers summing up to 16.

In this case, for num = 16, the sumOfThree function correctly responds with [], as there are no whole consecutive numbers that add up to 16.

Solution Implementation

1from typing import List  # Import List type from typing module for type hints.
2
3class Solution:
4    def sumOfThree(self, num: int) -> List[int]:
5        # Divide the number by 3 to find if there exists a sequence of 3 numbers that add up to 'num'.
6        quotient, remainder = divmod(num, 3)
7
8        # If the remainder is not zero, 'num' cannot be expressed as a sum of 3 consecutive numbers.
9        # Hence, return an empty list.
10        if remainder != 0:
11            return []
12      
13        # If the remainder is zero, construct the list of 3 consecutive numbers.
14        # Since 'quotient' is the middle number of the three consecutive numbers, we return
15        # a list containing 'quotient' - 1, 'quotient', and 'quotient' + 1.
16        return [quotient - 1, quotient, quotient + 1]
17
18# The function sumOfThree can now be used to check for any number if it can be expressed
19# as a sum of three consecutive integers. For example, calling sumOfThree(33) will return [10, 11, 12].
20

1class Solution {
2    // This method finds if the given number can be expressed as the sum of three consecutive integers.
3    public long[] sumOfThree(long num) {
4        // Check if the number is divisible by 3 to ensure it can be the sum of three consecutive integers.
5        if (num % 3 != 0) {
6            // If the number is not divisible by 3, return an empty array because it's not possible to find such three numbers.
7            return new long[] {};
8        }
9      
10        // Calculate the middle number of the three consecutive integers. 
11        // This works because the sum of three consecutive integers is always divisible by 3.
12        long middleNumber = num / 3;
13      
14        // Return an array containing the three numbers that sum up to the given number.
15        // middleNumber - 1, middleNumber, and middleNumber + 1 are three consecutive integers.
16        return new long[] {middleNumber - 1, middleNumber, middleNumber + 1};
17    }
18}
19

1#include <vector> // Include the header for using the vector container.
2
3// Define the Solution class as before.
4class Solution {
5public:
6    // Define the sumOfThree function which takes a long long integer 'num' and returns a vector of long long integers.
7    std::vector<long long> sumOfThree(long long num) {
8        // Check if 'num' is divisible by 3 since the sum of any three consecutive numbers is divisible by 3.
9        if (num % 3 != 0) {
10            // If 'num' is not divisible by 3, return an empty vector as it can't be the sum of three consecutive integers.
11            return {};
12        }
13      
14        // If it is divisible, calculate the middle number by dividing 'num' by 3.
15        long long middle = num / 3;
16      
17        // The three consecutive numbers would then be (middle - 1), 'middle', and (middle + 1).
18        // Return the vector containing these three numbers.
19        return {middle - 1, middle, middle + 1};
20    }
21};
22

1/**
2 * Finds if a number can be expressed as a sum of three consecutive numbers.
3 * If possible, it returns the three consecutive numbers as an array, otherwise returns an empty array.
4 * 
5 * @param {number} num - The number to be checked.
6 * @returns {number[]} An array containing three consecutive numbers that sum up to 'num', or an empty array if not possible.
7 */
8function sumOfThree(num: number): number[] {
9    // Check if 'num' is not divisible by 3. If so, there cannot be three consecutive numbers that add up to it.
10    if (num % 3 !== 0) {
11        return [];
12    }
13
14    // Calculate the middle number of the three consecutive numbers.
15    const middleNumber = Math.floor(num / 3);
16
17    // Return an array consisting of three consecutive numbers.
18    return [middleNumber - 1, middleNumber, middleNumber + 1];
19}
20

Time and Space Complexity

The given function sumOfThree aims to find if the input number num can be expressed as the sum of three consecutive integers.

Time Complexity:

The time complexity of the function is O(1). This is because the function consists of only a few constant-time operations:

The divmod function is called once, which takes constant time.
Checking the result of divmod using an if condition which is again a constant-time operation.
Returning a list with three elements or an empty list, both of which are constant-time operations.

There are no loops or recursive calls that depend on the size of the input, so the running time of the algorithm does not scale with the size of num.

Space Complexity:

The space complexity of the function is also O(1). This is because the function uses a fixed amount of space:

Storing the quotient x and the modulus mod uses a constant amount of space.
The output list has at most three integers, which is a constant size irrespective of the input size.

Therefore, no additional space that grows with the input size is required.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know