754. Reach a Number

98.10 %
class Solution {
    public int reachNumber(int target) {
        // Given the range[-10^9, 10^9], we can only solve it in O(logN)/O(sqrtN)/O(1)
        if (target < 0) {
            return reachNumber(-target);
        }
        // 1+2+...+K = (1+K)*K/2 >= target
        int K = (int)Math.sqrt(target);
        int sum = (1 + K) * K / 2;
        while (sum < target) {
            K++;
            sum += K;
        }
        // Find an i to subtract from this sequence
        // 1 + 2 +...(+/-) i +...+ K = target + residual -> residual < K
        if (sum == target || (target - sum) % 2 == 0) { // residual == 2i-> i < K
            return K;
        }
        // 1 + 2 +...(+/-) i +...+ K + K+1 = target + residual + K + 1 -> residual < K
        // K is even -> i = (residual + 1 + K) / 2 < (2K + 1) / 2 == K + 1/2 -> i < K
        // K is odd -> sum - K+1 + K+2 = sum + 1 -> residual + 1 == 2i -> i < (residual+1)/2 -> i < K
        return K + 1 + K % 2;
    }
}