1. 1.2에서 하신 것처럼 자리수 하나하나 놓고 하면 선형이 아니죠. Int64같이 총 자리수가 고정될 때 선형인데, Exponential 꼴에서 자리수가 고정이라고 가정하는건 좀 협소한 풀이인듯요. 1.2 에서의 복잡도를 요구했을거에요.
2. Running sum 쓰는 전형적인 접근이고 잘 하신 듯…
3. 검색해보면 나오는 유명한 문제인데 보통 이렇게 외워서 풀 수 있는 유명한 문제 안 내는데 인터뷰어가 빡대가리인듯요. 아니면 하드웨어쪽에서는 자주 쓰는 비트 연산인가요?