Reach a Number

这个题一看就是狗家的数学题. 又短又难. 这个题就是考察对数字的观察, 但是不看答案真的很难想到分类讨论的地方在target – sum(k)的奇偶性上. 因为偶数可以通过变换正负符号来找到target, 但是技术就不可以, 所以要通过再加一个或者两个来变换 target – sum(k)的奇偶.

class Solution {
    public int reachNumber(int target) {
        target = Math.abs(target);
        int k = 0;
        while(target > 0) {
            k++;
            target -= k;
        } // find k, where target - sum(k) < 0
        if(target % 2 == 0)
            return k;
        else {
            if((target - (k+1)) % 2 == 0)
                return k+1;
            else
                return k+2;
        }
    }
}