Cho đích trên đường thẳng vô hạn. Từ 0, bước i đi i đơn vị trái hoặc phải. Tìm số bước nhỏ nhất. Ví dụ đích=2 → 3 bước (0→1→-1→2).
Nếu đích âm lấy trị tuyệt đối. Tăng dần bước cho đến khi tổng ≥ đích và chênh lệch chẵn. Nếu chênh lệch lẻ, tăng thêm bước cho đến khi chẵn.
Ví dụ
#include<iostream> #include<cmath> using namespace std; int minStepToTarget(int target) { target = abs(target); int sum = 0, min_step = 0; while (sum < target || (sum - target) % 2 != 0) { min_step++; sum += min_step; } return min_step; } int main() { int target = 11; cout << "Minimum step to reach the target is: " << minStepToTarget(target); }
Kết quả
Minimum step to reach the target is: 5