題目描述

一個類卡布列克數,是一個擁有d個位數的正整數,它的平方乘冪可以分成擁有d個位數的右半部和d或d-1個位數的左半部,將右半部份加上左半部的值會剛好等於原始整數。在這裡的右半部可以是以0來開頭。



您將會得到兩個正整數p和q,p小於q。請寫出一個程式來找出有多少個類卡布列克數在p和q的範圍之間(包含p和q),並且將它們全部顯示出來。

原題網址

https://www.hackerrank.com/challenges/kaprekar-numbers

輸入格式

有兩行輸入,第一行為p,第二行為q。p和q的範為都在0到100000之間(不包含0和100000)。

輸出格式

輸出p到q的範圍中,所有的類卡布列克數,用空格分隔將它們放在同一行中。如果範圍中不存在類卡布列克數,輸出「INVALID RANGE」。

範例輸入

1
100

範例輸出

1 9 45 55 99

解題概念

原始的卡布列克數之定義是一個不是負數的整數,其平方乘冪可以被分成兩個部份,且這兩個部份相加後可以等於原本的整數,此數即為卡布列克數。如4879,48792=23804641,可以分成238和04641兩個部份,238+4641=4879,所以4879是卡布列克數。

但這個題目定義的類卡布列克數,兩部份中的右半部需為d個位數,且左半部只能是d個位數或是d-1個位數,因此4879不是類卡布列克數。

要判斷一個位數為d的整數n是否為類卡布列克數,需先計算n2的值。假設n2的位數為dd,若dd為偶數,則左半部的位數為d個,若dd為奇數,則左半部的位數為d-1個。從1002=10000與9992=998001可知,一個d位數的整數在平方乘冪計算之後的結果,位數必定為2d或是2d-1。

將平方乘冪的結果分成左右兩個部份之後,即可相加判斷是否等於原本的整數。

參考答案

import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        final int p = sc.nextInt();
        final int q = sc.nextInt();
        final StringBuilder sb = new StringBuilder();
        for (int n = p; n <= q; ++n) {
            final int d = String.valueOf(n).length();
            final int d_dec = d - 1;
            final String squareNText = String.valueOf((long) n * n);
            final int dd = squareNText.length();

            final int a, b;
            if (dd % 2 == 0) {
                a = Integer.parseInt(squareNText.substring(0, d));
                b = Integer.parseInt(squareNText.substring(d, d + d));
            } else {
                a = (d_dec == 0) ? 0 : Integer.parseInt(squareNText.substring(0, d_dec));
                b = Integer.parseInt(squareNText.substring(d_dec, d_dec + d));
            }
            if (a + b == n) {
                sb.append(n).append(" ");
            }
        }
        System.out.println((sb.length() == 0) ? "INVALID RANGE" : sb.toString().trim());
    }
}