Post date: Aug 23, 2014 1:1:38 AM
"Consider a number produced by taking '0.' and then concatenating each consecutive integer in order (0.1234567891011...). Find the first, 10th, 100th, 1000th, 10000th, 100000th, and 1000000th digits and multiply them."
We don't need to actually build out the string. We can load the numbers into a table and then just look at the places in the string where digits are expected to start, around the powers of 10. These indexes are just a running total of the lengths of the numbers (one digit plus one digit plus two digits etc). The only tricky part is that not every number will be on an exact boundary. In some cases, the indexes will be negative, and we need to backtrack from the previous record. SQL isn't like Python, which allows easy negative slicing, so it takes a case statement.
CREATE TABLE #Integers (i int not null primary key, runningtotal int null)
INSERT INTO #Integers (i) VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
; WITH Integers(i) AS
(
SELECT o.i +
(10 * d.i) +
(100 * h.i) +
(1000 * k.i) +
(10000 * k10.i) +
(100000 * k100.i)
FROM #Integers o
CROSS JOIN #Integers d
CROSS JOIN #Integers h
CROSS JOIN #Integers k
CROSS JOIN #Integers k10
CROSS JOIN #Integers k100
WHERE k100.i <= 1
)
INSERT INTO #Integers (i)
SELECT i
FROM Integers
WHERE i >= 10
DELETE FROM #Integers WHERE i = 0
-- Write the index of each number. The index is calculated by adding up the length to the end of the number preceding.
; WITH Digits (i, l) AS
(
SELECT i
, ISNULL(SUM(LEN(i)) OVER (ORDER BY i ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING),0) + 1
FROM #Integers
)
UPDATE i
SET runningtotal = d.l
FROM #Integers i
INNER JOIN Digits d ON i.i = d.i
-- This looks up the number that the power of ten falls within (the biggest index ending point equal to or less than the value).
-- It also returns the left position of the substring statement that pulls the correct digit.
-- In most cases, the actual number is on the index. In one case, it is less (the substring digit is negative).
-- To do this right, there would be an equivalent case statement on every digit, to count backward. I left it simple for readability.
; WITH Sums AS
(
SELECT MAX(CASE WHEN runningtotal <= 1 THEN i END) AS i1
, MAX(CASE WHEN runningtotal <= 1 THEN runningtotal END) AS dig1
, MAX(CASE WHEN runningtotal <= 10 THEN i END) AS i10
, MAX(CASE WHEN runningtotal <= 10 THEN runningtotal END) - 9 AS dig10
, MAX(CASE WHEN runningtotal <= 100 THEN i END) AS i100
, MAX(CASE WHEN runningtotal <= 100 THEN runningtotal END) - 99 AS dig100
, MAX(CASE WHEN runningtotal <= 1000 THEN i END) AS i1000
, MAX(CASE WHEN runningtotal <= 1000 THEN runningtotal END) - 999 AS dig1000
, MAX(CASE WHEN runningtotal <= 10000 THEN i END) AS i10000
, MAX(CASE WHEN runningtotal <= 10000 THEN runningtotal END) - 9999 AS dig10000
, MAX(CASE WHEN runningtotal <= 100000 THEN i END) AS i100000
, MAX(CASE WHEN runningtotal <= 100000 THEN runningtotal END) - 99999 AS dig100000
, MAX(CASE WHEN runningtotal <= 1000000 THEN i END) AS i1000000
, MAX(CASE WHEN runningtotal <= 1000000 THEN runningtotal END) - 999999 AS dig1000000
FROM #Integers
),
Digits AS
(
SELECT d1 = CONVERT(int,SUBSTRING(CONVERT(varchar(6),i1),
dig1,
1))
, d10 = CONVERT(int,SUBSTRING(CONVERT(varchar(6),i10),
dig10,
1))
, d100 = CONVERT(int,SUBSTRING(CONVERT(varchar(6),i100),
dig100,
1))
, d1000 = CONVERT(int,SUBSTRING(CONVERT(varchar(6),i1000),
dig1000
,1))
, d10000 = CONVERT(int,SUBSTRING(CONVERT(varchar(6),i10000),
CASE WHEN dig10000 > 0 THEN dig10000 ELSE LEN(i10000) + dig10000 END -- Counting backward from the end.
,1))
, d100000 = CONVERT(int,SUBSTRING(CONVERT(varchar(6),i100000),
dig100000,
1))
, d1000000 = CONVERT(int,SUBSTRING(CONVERT(varchar(6),i1000000),
dig1000000,
1))
FROM Sums
)
SELECT *, answer = d1 * d10 * d100 * d1000 * d10000 * d100000 * d1000000
FROM Digits
DROP TABLE #Integers