1342. Number of Steps to Reduce a Number to Zero

LeetCode の挑戦ログ

Problem

https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/

• 正の整数が渡される
• 偶数なら 2 で割る、奇数なら 1 を引く
• 0 になるまでの回数を数える

Solution

class Solution {
    public int numberOfSteps(int num) {
        return countSteps(num);
    }

    private int countSteps(int num) {
        int steps = 0;
        while (num != 0) {
            num = reduce(num);
            steps += 1;
        }

        return steps;
    }

    private int reduce(int num) {
        return num % 2 == 0 ? (num / 2) : (num - 1);
    }
}

Impressions

• 最初は再起で書いたけど、ループに書き直した
• Java には言語での末尾再帰最適化はないらしい
• Kotlin の tailrec は便利だな

再起で書いたやつ

class Solution {
    public int numberOfSteps(int num) {
        return countSteps(num, 0);
    }

    private int countSteps(int num, int steps) {
        num = reduce(num);
        steps += 1;

        if (num == 0) {
            return steps;
        }

        return countSteps(num, steps);
    }

    private int reduce(int num) {
        return num % 2 == 0 ? (num / 2) : (num - 1);
    }
}