Giả sử có số nguyên dương N, ta sắp xếp lại các chữ số (giữ nguyên hoặc thay đổi thứ tự) sao cho chữ số đầu không phải 0. Kiểm tra xem có thể sắp xếp thành lũy thừa của 2 hay không.
Ví dụ: N = 812, đầu ra = True (vì 128 = 2^7).
Giải pháp
Sinh tất cả lũy thừa của 2 ≤ 10^9, so sánh chuỗi ký tự đã sắp xếp:
- i := 1
- Khi i ≤ 1000000000:
- s := str(i), sắp xếp ký tự s
- t := str(n), sắp xếp ký tự t
- Nếu s == t: trả về True
- i := i * 2
- Trả về False
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
def solve(n):
i = 1
while i <= 1000000000:
s = str(i)
s = ''.join(sorted(s))
t = str(n)
t = ''.join(sorted(t))
if s == t:
return True
i = i * 2
return False
N = 812
print(solve(N))
Đầu vào
812
Đầu ra
True