牛客网 2018校招真题 招商银行信用卡 小招喵跑步

运维


Description

牛客网 2018校招真题 小招喵跑步

Solving Ideas

逆向思维，计算从终点到原点需要的最少步数

当x为偶数时，则x /= 2
当x为奇数时，如果(x + 1) / 2为偶数，则x++；如果(x – 1) / 2为偶数，则x–；
特别地，如x <= 3，则x–

对于任意的x，x属于整数，(x + 1) / 2为偶数 和 (x - 1) / 2为偶数 有且只有一个会成立。

Time complexity :




O


(


l


o


g


x


)



O(logx)



Space complexity :




O


(


1


)



O(1)


Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/** * @author wylu */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int x = Math.abs(Integer.parseInt(br.readLine()));

        int res = 0;
        while (x != 0) {
            if (x % 2 == 0) x >>= 1;
            else x += ((x + 1) / 2 % 2 == 0 && x > 3) ? 1 : -1;
            res++;
        }
        System.out.println(res);
    }
}