Post date: Aug 09, 2014 10:20:25 PM
"What is the largest 9 digit number, containing the digits 1 through 9 (in any order), which can be produced by multiplying a positive i by 1, then multiplying i by 2 and adding the result to the right side, then multiplying i by 3, etc, until you have filled exactly 9 digits?"
The problem here is a little contorted. The initial issue is figuring out the max value of the static number i. When you multiply by 1 and 2, it only works with a 4 digit number (which could become 5 digits when multiplied). A 5 digit number, when concatenated with the next product, would be 10 digits. It gets smaller from there, because if we want 3 products of the same number concatenated, together filling 9 digits, then the number must be no more than 3 digits.
After that, we just need to group each result set and make sure it has all the digits between 1 and 9, concatenate the results, and find the biggest.
-- The maximum value of i, theoretically, is 9999.
CREATE TABLE #Digits (i int not null primary key)
INSERT INTO #Digits VALUES (0), (1), (2), (3), (4), (5), (6), (7), (8), (9)
CREATE TABLE #Integers (i int not null primary key)
INSERT INTO #Integers
SELECT o.i +
(10 * d.i) +
(100 * h.i) +
(1000 * k.i)
FROM #Digits o
CROSS JOIN #Digits d
CROSS JOIN #Digits h
CROSS JOIN #Digits k
WHERE o.i + (10 * d.i) + (100 * h.i) + (1000 * k.i) > 0
-- For each integer, generate a dataset containing the number, the product for 1, the products for (1 and 2), the products for (1, 2, 3), etc, up to (1 ... 9).
-- We won't need more than 9 products, because the limit is 9 digits.
; WITH Combos (i, j, limit, prod) AS
(
SELECT i.i, n.i, limiter.i, CONVERT(varchar(9),i.i * n.i)
FROM #Integers i
CROSS JOIN #Digits n
INNER JOIN #Digits limiter
ON n.i <= limiter.i
AND limiter.i > 0
WHERE n.i > 0
),
-- Take each result set from the first CTE and concatenate the products.
-- Filter out any result sets that do not include exactly 9 distinct digits with no zeros. These are worthless.
Concatenated (result) AS
(
SELECT (SELECT '' + prod FROM Combos c2 WHERE c2.i = c.i AND c2.limit = c.limit ORDER BY j FOR XML PATH(''), TYPE).value('text()[1]','nvarchar(max)')
FROM Combos c
INNER JOIN #Digits d
ON c.prod LIKE '%' + CONVERT(char(1),d.i) + '%'
GROUP BY c.i, c.limit
HAVING COUNT(DISTINCT d.i) = 9 -- All 9 digits used
AND COUNT(d.i) = 9 -- All 9 digits used
AND MIN(d.i) > 0 -- No zeros in our results
)
SELECT MAX(result)
FROM Concatenated
WHERE LEN(result) = 9
DROP TABLE #Integers
DROP TABLE #Digits