Post date: Aug 05, 2014 1:15:15 AM
"Find all numbers under 1,000,000 that are palindromes in both base 10 and base 2, discarding leading zeros. Sum them."
The only tricky thing here is converting integer to binary. You can convert to hex easy enough, but binary takes a lookup. The rest is pretty trivial. Discarding leading zeros will basically drop out any even numbers, so it's not necessary to check them. Not that you'd notice. Either way, the results are instantaneous.
CREATE TABLE #Palindromes (i int not null primary key)
; WITH Ten(i) AS
(
SELECT 0
UNION ALL
SELECT i + 1
FROM Ten
WHERE i < 9
),
Integers(i) AS
(
SELECT CONVERT(varchar(7),
o.i +
(10 * d.i) +
(100 * h.i) +
(1000 * k.i) +
(10000 * k10.i) +
(100000 * k100.i))
FROM Ten o
CROSS JOIN Ten d
CROSS JOIN Ten h
CROSS JOIN Ten k
CROSS JOIN Ten k10
CROSS JOIN Ten k100
WHERE o.i % 2 = 1 -- Cut the palindromes in half by dropping out evens.
)
INSERT INTO #Palindromes (i)
SELECT i
FROM Integers
WHERE i = REVERSE(i)
CREATE TABLE #HexToBinary (hex char(1) PRIMARY KEY NOT NULL, [binary] char(4) NOT NULL)
INSERT INTO #HexToBinary VALUES
('0','0000'),
('1','0001'),
('2','0010'),
('3','0011'),
('4','0100'),
('5','0101'),
('6','0110'),
('7','0111'),
('8','1000'),
('9','1001'),
('A','1010'),
('B','1011'),
('C','1100'),
('D','1101'),
('E','1110'),
('F','1111')
-- Convert to varbinary, then to hex. Then convert each digit to binary using the lookup table.
-- SQL Server has no direct conversion to binary 1s and 0s.
; WITH BinaryStep1(i, hex) AS
(
SELECT i, CONVERT(varchar(6),CONVERT(varbinary(3),i), 2)
FROM #Palindromes
),
BinaryStep2 (i, binary) AS
(
SELECT i.i, h1.binary + h2.binary + h3.binary + h4.binary + h5.binary + h6.binary
FROM BinaryStep1 i
INNER JOIN #HexToBinary h1 ON h1.hex = SUBSTRING(i.hex,1,1)
INNER JOIN #HexToBinary h2 ON h2.hex = SUBSTRING(i.hex,2,1)
INNER JOIN #HexToBinary h3 ON h3.hex = SUBSTRING(i.hex,3,1)
INNER JOIN #HexToBinary h4 ON h4.hex = SUBSTRING(i.hex,4,1)
INNER JOIN #HexToBinary h5 ON h5.hex = SUBSTRING(i.hex,5,1)
INNER JOIN #HexToBinary h6 ON h6.hex = SUBSTRING(i.hex,6,1)
),
BinaryStep3 (i, binary) AS
(
-- This step strips leading zeros. It isn't necessary if we filter odds, but it's a useful line of code and I may be back to steal it later.
SELECT i, STUFF(binary, 1, PATINDEX('%[^0]%',binary) - 1, '')
FROM BinaryStep2
)
SELECT SUM(i)
FROM BinaryStep3
WHERE binary = REVERSE(binary)
DROP TABLE #HexToBinary
DROP TABLE #Palindromes