_650. 2 Keys Keyboard.md

650. 2 Keys Keyboard

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : August 19, 2024

Last updated : August 19, 2024

---

Related Topics : Math, Dynamic Programming

Acceptance Rate : 59.61 %

---

Notes:

Not that efficient but passed with AC. To improve runtime, can keep a cache or maxheap based off the currLen so far and return early if it's not a useful propogation.

---

Solutions

• m650.py

Python

m650.py

class Solution:
    def minSteps(self, n: int) -> int:
        self.val = inf

        def propogate(currLen: int = 1, copyLen: int = 0, steps: int = 0) -> None :
            if currLen == n :
                if self.val > steps :
                    self.val = steps
                return

            if currLen != copyLen and currLen + currLen <= n:
                propogate(currLen, currLen, steps + 1)

            if copyLen != 0 and copyLen + currLen <= n :
                propogate(currLen + copyLen, copyLen, steps + 1)

        propogate()
        return self.val