모든 챌린지
보통 0명 해결 정답률 0%

Kaprekar Number

Check whether the square of a d-digit number splits into a left part and a d-digit right part that add up to the number.

배우게 될 내용

  • Split a number into a left and right part at a digit position
  • Use the digit count of n to choose the split
  • Apply every condition of a definition, including the non-zero rule

문제

번역본 보기

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.

제약 조건

1 ≤ n ≤ 10^9

예시

예시 1
입력:
n = 45

예상 출력:
expected = True
입력:
long long n = 45;

예상 출력:
bool expected = true;
입력:
long n = 45;

예상 출력:
bool expected = true;

설명

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.

예시 2
입력:
n = 4879

예상 출력:
expected = False
입력:
long long n = 4879;

예상 출력:
bool expected = false;
입력:
long n = 4879;

예상 출력:
bool expected = false;

설명

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.

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

Let d be the number of digits of n and work with n² in a 64-bit integer.

힌트 2

With p = 10^d, the right part is n² mod p and the left part is n² / p.

힌트 3

Reject the number if the right part is 0, even when the sum would match.

예상 복잡도

O(d) time for d digits, O(1) extra space

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.