สมมติว่าคุณกำลังยืนอยู่ที่ตำแหน่ง 0 บนเส้นจำนวนอนันต์ ตอนนี้มีเป้าหมายที่ตำแหน่งเป้าหมาย ในแต่ละการเคลื่อนไหว คุณสามารถไปทางซ้ายหรือทางขวาก็ได้ ระหว่างการเคลื่อนไหวครั้งที่ n (เริ่มจาก 1) คุณต้องก้าว n ขั้น เราต้องหาจำนวนขั้นขั้นต่ำที่จำเป็นในการไปถึงปลายทาง ดังนั้นหากอินพุตเหมือนเป้าหมาย =3 เราก็ต้องมี 2 ขั้นตอน จาก 0 ถึง 1 จาก 1 ถึง 3
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- target :=|target|, cnt :=0
- ในขณะที่เป้าหมาย> 0,
- ลดลง 1 ต่อ
- เป้าหมาย :=เป้าหมาย –cnt
- ถ้าเป้าหมายเป็นเลขคู่ ให้คืนค่า cnt มิฉะนั้น cnt + 1 + cnt mod 2
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int reachNumber(int target) {
target = abs(target);
int cnt = 0;
while(target > 0){
target -= ++cnt;
}
return target % 2 == 0? cnt : cnt + 1 + cnt % 2;
}
};
main(){
Solution ob;
cout << (ob.reachNumber(3));
} อินพุต
3
ผลลัพธ์
2
