【Video】Give me 10 minutes - How we think about a solution - No difficult mathematics
Welcome to my post! This post starts with "How we think about a solution". In other words, that is my thought process to solve the question. This post explains
Welcome to my post! This post starts with "How we think about a solution". In other words, that is my thought process to solve the question. This post explains how I get to my solution instead of just posting solution codes or out of blue algorithms. I hope it is helpful for someone.


# Intuition
Create 3 as many as possible.

---

# Solution Video

### ⭐️⭐️ Don't forget to subscribe to my channel! ⭐️⭐️

https://youtu.be/q3EZpCSn6lY

■ Timeline of the video
`0:00` Read the question of Integer Break
`0:16` How we think about a solution
`5:08` Demonstrate solution with an example
`9:23` Coding
`12:22` Time Complexity and Space Complexity

**■ Subscribe URL**
http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1

Subscribers: 2,617
My initial goal is 10,000
Thank you for your support!

---

# Approach

## How we think about a solution.

When looks like we have a lot of answers, I always start with the simplest examples. Let's start from `n = 2 until 10` and `k >= 2`.

When divided `2` into `1 + 1`, the product does not exceed `2`, so no further division is possible.

```
1 * 1 < 2
```

When divided `3` into `1 + 2`, the product does not exceed `3`, so no further division is possible.

```
1 * 1 * 1 < 3
1 * 2 < 3
```

`4` can be divided into `2 + 2` (even though they are equal to `4`, we split for convenience).

```
1 * 1 * 1 * 1 < 4
1 * 1 * 2 < 4
2 * 2 = 4 ⭐️
```

Splitting `5` into `3 + 2` yields a higher product. `2` and `3` cannot be further divided based on the previous steps.

```
1 * 1 * 1 * 1 * 1 < 5
1 * 1 * 1 * 2 < 5
1 * 1 * 3 < 5
1 * 2 * 2 < 5
3 * 2 > 5 ⭐️
4 * 1 < 5 (we can divide 4 into 2 * 2)
```

From examples above, we can divide the original numbers into small number from `4`.

What is the biggest number after we break down the original number? It's `3` because It's the biggest and cannot be splitted into small numbers anymore.

Let's comfirm with `6`. Focus on over `6` cases.
```
2 * 2 * 2 = 8
3 * 3 = 9
4 * 2 = 8 (= 2 * 2 * 2)
```

Splitting `6` into `3 + 3` yields a higher product.


---


⭐️ Points
 
We break down the original number because there is a pattern to get bigger number compared with the original number.

For example,
```
n = 5
3 * 2 > 5

Let's say we have another 2.
6 * 2 > 5 * 2 (5 is original number)
```

The biggest number which doesn't have the pattern to get bigger number by splitting is `3`. Look at case `3` above again.

As you can see, all the original numbers over 3 has the pattern. That's why we break down the original numbers and get `3` as many as possible.

Look at more examples below.

---

From `7` to `10`,

Splitting `7` into `3 + 2 + 2` yields a higher product. `3` and `2` cannot be further divided.

Splitting `8` into `3 + 3 + 2` yields a higher product. `3` and `2` cannot be further divided.

Splitting `9` into `3 + 3 + 3` yields a higher product. `3` cannot be further divided.

Splitting `10` into `3 + 3 + 2 + 2` yields a higher product. `3` and `2` cannot be further divided.


## How it works

Let's see an example with `10`.

We try to create `3` as many as possible, so

```
10 // 3 = 3

threes: 3
remainder: 1
```
Easy! Let's multiply all the numbers.
```
3 * 3 * 3 * 1 = 27 (1 is remainder)
```
Wait! Description says when `n = 10`, output should be `36`.

Why this happened?

When `n = 10`, output is `36`. but our answer is `27` which is `9 difference`. Let's simplify `3 * 3 * 3 * 1`.
```
9 * 3 * 1
```
Let's focus on `3 * 1` part. the reason why we get `27` is we have 3 nines right?
```
9 * 3 * 1
↓
9 * 3
```

But what if we create `2 * 2` instead of `3 * 1`? we can do that because total of `2 + 2` and `3 + 1` is the same.

total is the same but answer of multiplication is different `4` vs `3`.

From the example, 


---

⭐️ Points

When we have `1` as a `remainder`, we will get bigger number if we borrow `1` from one of 3s and create `2 * 2` instead of `3 * 1`.

Simply, we don't use `1` because `1` doesn't change an answer in multiplication. On the other hand, we know that `2` makes the number double.

---



---


⭐️ In summary:

1. Create as many threes as possible.
2. When there's a remainder of 1, convert `3 * 1` to `2 * 2(or 4)`.


---

Let's see a real algorithm!


**Algorithm Overview:**

1. Check if n is 2 or 3 and return the appropriate value.
2. Divide n into as many threes as possible and handle the remainder for maximizing the product.
3. Multiply the result based on the division and the remainder.

**Detailed Explanation:**

1. **Check for n being 2 or 3:**
   - If \(n\) equals 2, return 1 (as specified in the problem).
   - If \(n\) equals 3, return 2 (as specified in the problem).

2. **Divide n into as many threes as possible:**
   - Calculate the maximum number of threes that can be obtained from \(n\) using integer division (\(n // 3\)).
   - Calculate the remainder after dividing \(n\) by 3 (\(n \% 3\)).

3. **Handle remainder to maximize the product:**
   - If the remainder is 1:
     - Borrow one from a three to make two 2s by decrementing threes by 1 and setting remainder to 4.
   - If the remainder is 0:
     - Set remainder to 1 (no need to borrow).

4. **Calculate the final product:**
   - Calculate the product by raising 3 to the power of threes (\(3\) raised to the power of \(threes\)) and multiplying by the remainder.

Here's the provided code implementing the above steps:

# Complexity
- Time complexity:$$ O(log(threes))$$

The time complexity for raising a number to the power of another number depends on the method used for exponentiation. In the case of (3 ** threes), where threes is an integer, the time complexity is generally O(log(threes)) using the binary exponentiation (also known as exponentiation by squaring) algorithm.

Binary exponentiation reduces the number of multiplications needed to compute an exponent by breaking down the exponent into a sum of powers of 2. This algorithm allows for more efficient calculations compared to a naive approach, which would require threes multiplications.

Hence, raising 3 to the power of threes (3 ** threes) typically has a time complexity of O(log(threes)) using efficient exponentiation algorithms.

- Space complexity: $$O(1)$$

```python []
class Solution:
    def integerBreak(self, n: int) -> int:
        if n == 2:
            return 1
        if n == 3:
            return 2

        # Try to divide n into as many threes as possible
        threes = n // 3
        remainder = n % 3

        if remainder == 1:
            threes -= 1 # remove 3 * 1
            remainder = 4 # create 2 * 2
        elif remainder == 0:
            remainder = 1 # when remainder is 0, set 1 which doesn't affect your answer.

        return (3 ** threes) * remainder
```
```javascript []
/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {
    if (n === 2) {
        return 1;
    }
    if (n === 3) {
        return 2;
    }

    // Try to divide n into as many threes as possible
    let threes = Math.floor(n / 3);
    let remainder = n % 3;

    if (remainder === 1) {
        threes -= 1; // remove 3 * 1
        remainder = 4; // create 2 * 2
    } else if (remainder === 0) {
        remainder = 1; // when remainder is 0, set 1 which doesn't affect your answer.
    }

    return Math.pow(3, threes) * remainder;    
};
```
```java []
class Solution {
    public int integerBreak(int n) {
       if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }

        // Try to divide n into as many threes as possible
        int threes = n / 3;
        int remainder = n % 3;

        if (remainder == 1) {
            threes -= 1; // remove 3 * 1
            remainder = 4; // create 2 * 2
        } else if (remainder == 0) {
            remainder = 1; // when remainder is 0, set 1 which doesn't affect your answer.
        }

        return (int) (Math.pow(3, threes) * remainder);        
    }
}
```
```C++ []
class Solution {
public:
    int integerBreak(int n) {
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }

        // Try to divide n into as many threes as possible
        int threes = n / 3;
        int remainder = n % 3;

        if (remainder == 1) {
            threes -= 1; // remove 3 * 1
            remainder = 4; // create 2 * 2
        } else if (remainder == 0) {
            remainder = 1; // when remainder is 0, set 1 which doesn't affect your answer.
        }

        return (int) (pow(3, threes) * remainder);        
    }
};
```

---

Thank you for reading my post.
⭐️ Please upvote it and don't forget to subscribe to my channel!

⭐️ Subscribe URL
http://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1

https://youtu.be/5_lYYnSsOGU
['Math', 'Dynamic Programming', 'C++', 'Java', 'Python3', 'JavaScript']