Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Số Kaprekar

Kiểm tra xem bình phương của một số có d chữ số có tách được thành phần trái và phần phải d chữ số với tổng bằng chính số đó hay không.

Bạn sẽ học được gì

  • Tách một số thành phần trái và phần phải tại một vị trí chữ số
  • Dùng số chữ số của n để chọn vị trí cắt
  • Áp dụng đầy đủ mọi điều kiện của định nghĩa, kể cả điều kiện khác 0

Đề bài

Xem bản gốc (English)

Bình phương số đã cho rồi cắt dãy chữ số thập phân của kết quả làm hai: phần phải là d chữ số cuối, với d là số chữ số của số ban đầu, còn phần trái là những gì còn lại (bằng 0 nếu không còn gì). Số đó là số Kaprekar nếu phần phải khác 0 và tổng hai phần bằng đúng số ban đầu. Ví dụ, 297 có 3 chữ số và 297² = 88209; phần phải là 209, phần trái là 88, và 88 + 209 = 297.

Hãy viết kaprekar_number(n).

Mỗi tài liệu định nghĩa số Kaprekar hơi khác nhau. Ở bài này, vị trí cắt luôn cố định ở d chữ số tính từ bên phải (đây là phiên bản trong OEIS A053816, và là trường hợp p = d trong định nghĩa của Wikipedia); một số tài liệu thử thêm các vị trí cắt khác, khi đó những số như 4879 sẽ được chấp nhận, trong khi phiên bản này thì không. Phần phải được phép có chữ số 0 ở đầu (với 703, 703² = 494209 cho ra 494 và 209), và phần phải phải khác 0, nên 10, 100, ... không phải số Kaprekar. 1 là số Kaprekar: 1² = 1 cho phần trái 0 và phần phải 1.

Đầu vào

n: Số cần kiểm tra.

Đầu ra

Trả về true nếu n là số Kaprekar theo định nghĩa trên, ngược lại trả về false.

Ràng buộc

1 ≤ n ≤ 10^9

Ví dụ

Ví dụ 1
Đầu vào:
n = 45

Kết quả mong đợi:
expected = True
Đầu vào:
long long n = 45;

Kết quả mong đợi:
bool expected = true;
Đầu vào:
long n = 45;

Kết quả mong đợi:
bool expected = true;

Giải thích

45 có 2 chữ số và 45² = 2025: phần trái là 20, phần phải là 25, và 20 + 25 = 45, nên kết quả là true.

Ví dụ 2
Đầu vào:
n = 4879

Kết quả mong đợi:
expected = False
Đầu vào:
long long n = 4879;

Kết quả mong đợi:
bool expected = false;
Đầu vào:
long n = 4879;

Kết quả mong đợi:
bool expected = false;

Giải thích

4879 có 4 chữ số và 4879² = 23804641: phần trái là 2380, phần phải là 4641, và 2380 + 4641 = 7021 chứ không phải 4879, nên kết quả là false.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Gọi d là số chữ số của n và tính n² bằng kiểu số nguyên 64 bit.

Gợi ý 2

Đặt p = 10^d, khi đó phần phải là n² mod p và phần trái là n² / p.

Gợi ý 3

Loại số đó nếu phần phải bằng 0, kể cả khi tổng có khớp.

Độ phức tạp mong đợi

thời gian O(d) với d chữ số, bộ nhớ phụ O(1)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.