# 6.10.2023 [343. Integer Break]

Max multiplication of the number split

6.10.2023

343. Integer Break medium
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/361

Problem TLDR

Max multiplication of the number split

Intuition

We can search from all possible splits. The result will only depend on the input n, so can be cached.

Approach

• one corner case is the small numbers, like 2, 3, 4: ensure there is at least one split happen

Complexity

• Time complexity:
  O(n^2), recursion depth is n and another n is in the loop. Without cache, it would be n^n

• Space complexity:
  O(n)

Code

    val cache = mutableMapOf<Int, Int>()
    fun integerBreak(n: Int, canTake: Boolean = false): Int = 
      if (n == 0) 1 else cache.getOrPut(n) {
        (1..if (canTake) n else n - 1).map {
          it * integerBreak(n - it, true)
        }.max()
      }