LintCode 797 · Reach a Number.java

	// Approach #1 - Math - T O(sqrt(target))
	public class Solution {
	/**
	* @param target: the destination
	* @return: the minimum number of steps
	*/
	public int reachNumber(int target) {
	// Write your code here
	target = Math.abs(target);
	int position = 0, step = 1;
	while (position < target) {
	position += step;
	step++;
	}
	step--;
	if (position == target) {
	return step;
	}
	// remember if the diff is even, it is achievable with same steps, just flip the 2, or 4, or other something that you already have.
	int diff = position - target;
	if (diff % 2 == 0) {
	return step;
	} else if ((step + 1) % 2 == 1) {
	// if the diff is odd, and the next step is odd, then the next step will make it even.
	return step + 1;
	} else {
	// if the diff is odd, and the next step is even, then the next of the next will make it even.
	return step + 2;
	}
	}
	}

view raw LintCode 797 · Reach a Number.java hosted with ❤ by GitHub