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

題目描述

一個類卡布列克數,是一個擁有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。

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

參考答案

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章