Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero

1. Mở đầu

Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.

2. Đề bài

Cho một số nguyên num, trả về kết quả là số bước để giảm số num về 0.
Với mỗi bước, nếu số hiện tại là số chẵn thì chia cho 2, nếu là số lẻ thì trừ đi 1.

Điều kiện bài toán:

  • 0 <= num <= 106.

Bài toán minh họa 1:

Input: num = 14
Output: 6
Explanation: 
Step 1) 14 is even; divide by 2 and obtain 7. 
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3. 
Step 4) 3 is odd; subtract 1 and obtain 2. 
Step 5) 2 is even; divide by 2 and obtain 1. 
Step 6) 1 is odd; subtract 1 and obtain 0.

Bài toán minh họa 2:

Input: num = 8
Output: 4
Explanation: 
Step 1) 8 is even; divide by 2 and obtain 4. 
Step 2) 4 is even; divide by 2 and obtain 2. 
Step 3) 2 is even; divide by 2 and obtain 1. 
Step 4) 1 is odd; subtract 1 and obtain 0.

Bài toán minh họa 3:

Input: num = 123
Output: 12

3. Phân tích

Âu kê! Bài này nhìn chung đơn giản thôi các bạn ơi, cho một số num, là số chẵn thì chia 2, là số lẻ thì trừ đi 1, với mỗi lần như thế thì tính là một bước. Trả kết quả về là số bước thôi. Dễ mà đúng không ạ?

4. Chạy code bằng cơm

Đầu tiên thì chúng ta cần một biến chứa số nguyên step để đếm số bước để giảm số num về 0.
leetcode-1342-1

Vì không biết trước sẽ cần bao nhiêu bước để giảm số num về 0, nên ta sẽ làm vòng lặp while với điều kiện dừng là num > 0, chứ num mà về 0 rồi thì dừng chứ còn gì nữa. Đúng không ạ?
leetcode-1342-2

Tiếp theo, nếu số num hiện tại đang là số chẵn thì ta chia num cho 2 và gán kết quả ấy cho num luôn, đồng thời step tăng thêm 1:
leetcode-1342-3

Nhưng nếu số num hiện tại là số lẻ thì ta trừ num cho 1 đồng thời vẫn tăng step thêm một bước.
leetcode-1342-4

Thế là xong, bài này cũng không quá phức tạp, chúng ta đến bước tiếp theo thôi!

5. Code thôi nào

Code của chúng ta sẽ như sau:

public int numberOfSteps(int num) {
  int step = 0;
  while (num > 0) {
      if (num %2 == 0) {
          num /= 2;
          step++;
      }
      else{
          num -= 1;
          step++;
      }  
  }

  return step;
}

6. Kết thúc

Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!