leetcode hard : Number of Digit One

https://leetcode.com/problems/number-of-digit-one/

Number of Digit One - LeetCode

 

n이 범위가 10^9로 상당히 크다.

Math 문제가 틀림없다.

 

일단 Bruteforce부터 해볼까?

Approach 1 : Brute force

class Solution:
    def countDigitOne(self, n: int) -> int:
        def count(num):
            if num == 0: return 0
            c = 1 if num % 10 == 1 else 0
            c += count(num // 10)
            return c

        answer = 0
        for i in range(n + 1):
            answer += count(i)
        return answer

한 숫자를 계산할때마다 그 숫자의 자릿수(log N)만큼 recursive call이 일어난다.

O(N log N)의 시간복잡도

그리고 recursive call의 함수 스택을 고려하면 O(log N)의 공간복잡도.

 

안돌려봐도 TLE가 뜰것이라 확신

 

Approach 2 : Memoization

class Solution:
    def countDigitOne(self, n: int) -> int:
        memo = {0:0}

        def count(num):
            if num in memo : return memo[num]
            c = 1 if num % 10 == 1 else 0
            c += count(num // 10)
            memo[num] = c
            return c

        answer = 0
        for i in range(n + 1):
            answer += count(i)
        return answer

count 함수의 결과를 메모해놓는 방법

하지만 이거 memoization의 효율이 생각보다 좋지 않다.

그리고 O(N)의 시간복잡도를 어떻게 달성한다 해도 n은 최대 10^9기 때문에

TLE가 뜰수밖에 없다.

O(N)보다 빠른 방법을 찾아야한다. (log N)

 

이건 사실 솔루션을 봐도 잘 모르겠어서 설명을 열심히 찾아다녔다.

자릿수별로 1의 개수를 세는 방식이라고 한다.

 

For people who doesn't understand the author's explanations, just look at some examples: Let n = 4560000 How many nums with "1" at the thousand's position? 4551000 to 4551999 (1000) 4541000 to 4541999 (1000) 4531000 to 4531999 (1000) ... 1000 to 1999 (1000) That's 456 * 1000 What if n = 4561234? 4561000-4561234 (1234+1) 4551000 to 4551999 (1000) 4541000 to 4541999 (1000) 4531000 to 4531999 (1000) ... 1000 to 1999 (1000) That's 456 * 1000 + 1234 + 1 What if n = 4562345? 4561000-4561999 (1000) 4551000 to 4551999 (1000) 4541000 to 4541999 (1000) 4531000 to 4531999 (1000) ... 1000 to 1999 (1000) That's 456*1000 + 1000 Same for hundred's position. Let n = 4012 How many nums with "1" at the hundred's position? 3100-3999 (100) 2100-2999 (100) 1100-1999 (100) 100 to 199 (100) That's 4 * 100 Let n = 4111 4100-4111 ( 11 + 1) 3100-3999 (100) 2100-2999 (100) 1100-1999 (100) 100 to 199 (100) That's 4 * 100 + 11 + 1 Let n = 4211 4100-4199 (100) 3100-3999 (100) 2100-2999 (100) 1100-1999 (100) 100 to 199 (100) That's 4 * 100 + 100 Same for ten's digit Let n = 30 How many nums with "1" at the ten's position? 210-219 (10) 110-119 (10) 10-19 (10) That's 3 * 10 Let n = 312 310-312 (2 + 1) 210-219 (10) 110-119 (10) 10-19 (10) That's 3 * 10 + 2 + 1 Let n = 322 310-319 (10) 210-219 (10) 110-119 (10) 10-19 (10) That's 3 * 10 + 10 Same for one's digit Let n = 30 How many nums with "1" at the one's position? 21 (1) 11 (1) 1(1) That's 3 * 1 Let n = 31 How many "1" are there at the one's position? 31 (1) 21 (1) 11 (1) 1 (1) That's 3 * 1 + 1 Let n = 32 How many "1" are there at the one's position? 31 (10) 21 (10) 11 (10) 1 (10) That's 3 * 1 + 1 Let n = 3 only 1 (10 of "1" at one's position) That's 0 * 1 + 1

이렇게 보니까 조금은 이해가 된다. 그래도 난 다음 댓글에 너무 공감이된다.

 

 

class Solution:
    def countDigitOne(self, n):
        ans, m = 0, 1
        while m <= n:
            ans += (n//m + 8) // 10 * m + (n//m % 10 == 1) * (n%m + 1)
            m *= 10
        return ans