[HackerRank]類卡布列克數(Modified Kaprekar Numbers)

題目描述

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

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

原題網址

輸入格式

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

輸出格式

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

範例輸入

範例輸出

解題概念

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

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

要判斷一個位數為d的整數n是否為類卡布列克數，需先計算n²的值。假設n²的位數為dd，若dd為偶數，則左半部的位數為d個，若dd為奇數，則左半部的位數為d-1個。從100²=10000與999²=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());
    }
}