Code thay số bị sai

[Duc_Thanh_Trinh (Đức Thành Trịnh)]

bài này theo em nghĩ là cho dù làm thế nào thì n-1 chia 2 vẫn giảm nhanh hơn n+1 chia 2 nhưng kết quả là sai 3 test nên ai có thể thông não giùm em được không ạ

[rogp10]

Không phải lúc nào cũng vậy, ví dụ n = 2^k - 1.
Để xử lí một bit 1 phải tốn ít nhất hai bước, vì vậy phải giảm số bit 1.

Với trường hợp …01 thì trừ 1 là tối ưu, nhưng …0(1)* thì +1 mới đúng. Vậy làm sao để phân biệt?

…01 thì x & (x+1) sẽ bằng x & (x-1) = …00
…0(1)* thì x & (x+1) bé hơn.

[SITUVN.gcd]

Số 2^{5}-1=31 sẽ cần:
Nếu làm theo cách của bạn:

1. Trừ 1 = 30
2. Chia 2 = 15
3. Trừ 1 = 14
4. Chia 2 = 7
5. Trừ 1 = 6
6. Chia 2 = 3
7. Trừ 1 = 2.
8. Chia 2 = 1

Làm cách tối ưu hơn:

1. Cộng 1 = 32
2. Chia 2 = 16
3. Chia 2 = 8
4. Chia 2 = 4
5. Chia 2 = 2
6. Chia 2 = 1

Bit 1 cần 2 bước, bit 0 chỉ cần 1 bước. Hãy tối ưu sao cho giảm số bit 1 nhiều nhất.

[Duc_Thanh_Trinh (Đức Thành Trịnh)]

cảm ơn anh ạ em fix đc rồi

[Duc_Thanh_Trinh (Đức Thành Trịnh)]

em cảm ơn ạ