Question: Challenge: Number of Palindromic Numbers
Challenge: provide the implementation of a custom Delphi function to locate all palindromic numbers from 1 to maxNumber and return the number of found palindromes as a result of the function.
The code is submitted for the Number of Palindromic Numbers Delphi Challenge
Answer: Number of palindromic numbers entry by Wim Adriaensen (Belgium):
function WimAdriaensen_NumberOfPalindromes(const maxNumber : int64) : int64;
var
j: integer;
Number, diff: int64;
s: string;
len: integer;
const powers: array[ 0..18] of int64 = (
1,
1,
1,
10,
10,
100,
100,
1000,
1000,
10000,
10000,
100000,
100000,
1000000,
1000000,
10000000,
10000000,
100000000,
100000000) ;
function EqualLength( AllowLeading0: Boolean): int64;
var
n: integer;
begin
n:= Ord( s[ 1])- 48;
if AllowLeading0 then
Result:= n * powers[ len]
else
Result:= (n - 1) * powers[ len];
if len > 2 then begin
s:= copy( s, 2, len-2) ;
len:= length( s) ;
Result:= Result+ EqualLength( True) ;
end else
INC( Result) ;
end;
begin
Number:= MaxNumber;
//Turn Number into a smaller number so that each mirroring char at the end
// is greater or equal to the corresponding char in the front
//This new number has the same number of palindromes
//e.g. 13620 -> 13619 (1xxx0 : 1 is less than 0)
// -> 13599 (x3x1x : 3 is less than 1)
s:= inttostr( Number) ;
len:= length( s) ;
for j := 1 to len div 2 do
begin
if s[ j] > s[ len- j+ 1] then
begin
diff:= 1+ StrToInt64( copy( s, len- j+ 1, len)) ;
Number:= Number - diff;
s:= inttostr( Number) ;
len:= Length( s) ;
end;
end;
Result:= 0;
//All shorter strings 1..9, 10..99, 100..999 etc.
for j:= 1 to len- 1 do
Result:= Result+ 9 * powers[ j];
//strings of equal length
Result:= Result+ EqualLength( False) ;
end;
Test data: MAXNUMBER = 10 000 000
Wim's speed result: 4200 nanoseconds.
Explore the list of all accepted entries for the Number of Palindromic Numbers Delphi Challenge.
