LeetCode Entry

343. Integer Break

6.10.2023 medium 2023 kotlin

Max multiplication of the number split

343. Integer Break medium blog post substack image.png

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()
      }