Đề bài
Square the number and cut the decimal digits of the square in two: the right part is the last d digits, where d is the number of digits of the original number, and the left part is whatever is left (0 if nothing is left). The number is a Kaprekar number if the right part is not zero and the two parts add up to the number. For example, 297 has 3 digits and 297² = 88209; the right part is 209, the left part is 88, and 88 + 209 = 297.
Implement kaprekar_number(n).
Definitions differ between sources. Here the split is always fixed at d digits from the right (the version listed in OEIS A053816, and the p = d case of the Wikipedia definition); some sources also try other split points, which would accept numbers like 4879 that this version rejects. The right part may have leading zeros (for 703, 703² = 494209 gives 494 and 209), and it must not be zero, so 10, 100, ... are not Kaprekar numbers. 1 is a Kaprekar number: 1² = 1 gives left 0 and right 1.
Input
n: The number to test.
Output
Return true if n is a Kaprekar number under the definition above, otherwise false.
Ràng buộc
1 ≤ n ≤ 10^9
Ví dụ
Đầ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 has 2 digits and 45² = 2025: the left part is 20 and the right part is 25, and 20 + 25 = 45, so the answer is true.
Đầ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 has 4 digits and 4879² = 23804641: the left part is 2380 and the right part is 4641, and 2380 + 4641 = 7021, not 4879, so the answer is false.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Let d be the number of digits of n and work with n² in a 64-bit integer.
Gợi ý 2
With p = 10^d, the right part is n² mod p and the left part is n² / p.
Gợi ý 3
Reject the number if the right part is 0, even when the sum would match.
Độ phức tạp mong đợi
O(d) time for d digits, O(1) extra space
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.