1342-kir3i.md

1342. Number of Steps to Reduce a Number to Zero

Solution

• 시간복잡도: O(logN)

• 알고리즘

  재귀

• 풀이설명

  주어진 연산을 몇 회 수행하면 0이 될지 구하는 문제입니다. 재귀함수를 구현하여 해결했습니다.

• 소스코드

  • C++

    class Solution {
    public:
        int numberOfSteps (int num) {
            if(!num)        return 0;
            else if(num&1)  return numberOfSteps(num - 1) + 1;
            else            return numberOfSteps(num / 2) + 1;
        }
    };

  • Python

    class Solution:
        def numberOfSteps(self, num):
            if num == 0:
                return 0
            elif num % 2 == 0:
                return self.numberOfSteps(num//2) + 1
            else:
                return self.numberOfSteps(num-1) + 1

  • Java

    class Solution {
        public int numberOfSteps (int num) {
            if(num == 0)        return 0;
            else if(num%2 == 0) return numberOfSteps(num / 2) + 1;
            else                return numberOfSteps(num - 1) + 1;
        }
    }