Straightforward Python O(n)


  • 0
    S
    class Solution(object):
        def magicalString(self, n):
            """
            :type n: int
            :rtype: int
            """
            # base case
            # string:    1 2 2
            # occurrence:1 2
            if n <= 0:
                return 0
            if n <= 3:
                return 1
            num_one = 1
            nums = [1, 2, 2]
            i = 1
            add_one = True # shall we add ones or twos next
            while len(nums) < n:
                i += 1
                if add_one:
                    num_one += min(n - len(nums), nums[i])
                    nums += [1 for _ in range(nums[i])]
                    add_one = False
                else:
                    nums += [2 for _ in range(nums[i])]
                    add_one = True
            return num_one

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.