Post date: Jan 17, 2015 11:5:54 PM
"Find the smallest number which 5 permutations of its digits are perfect cubes."
While building permutations is fun (I will include it at the end of the post), it's not an efficient way to solve the problem. It takes time. The fastest solution comes fromn sorting each string alphabetically. Two cubes that are permutations of the same number will be the same when sorted. Do a simple grouping on that column. Much faster.
-- Take a random guess and assume that the answer is not bigger than 10000 cubed.
CREATE TABLE #Cubes (c VARCHAR(16) PRIMARY KEY NOT NULL)
; WITH Integers (i) AS
(
SELECT 1
UNION ALL
SELECT i + 1
FROM Integers
WHERE i < 10000
),
Cubes (c) AS
(
SELECT CONVERT(varchar(16),POWER(CONVERT(bigint,i), 3))
FROM Integers
)
INSERT INTO #Cubes
SELECT c
FROM Cubes
OPTION (MAXRECURSION 10000)
-- Split the numbers into their digits, because SQL has no quick builtin function to sort strings.
; WITH Splits (c, i, j) AS
(
SELECT c, 1, SUBSTRING(c,1,1)
FROM #Cubes
UNION ALL
SELECT c.c, i.i + 1, SUBSTRING(c.c,i.i + 1,1)
FROM #Cubes c
INNER JOIN Splits i
ON c.c = i.c
AND i.i < LEN(c.c)
)
SELECT c, j
INTO #Splits
FROM Splits
; WITH Sorted (c, sort) AS
(
SELECT c.c,
(SELECT '' + j FROM #Splits s WHERE s.c = c.c ORDER BY s.j FOR XML PATH(''), TYPE).value('text()[1]','nvarchar(max)')
FROM #Cubes c
)
SELECT TOP 1 MIN(CONVERT(bigint,c))
FROM Sorted
GROUP BY sort
HAVING COUNT(*) = 5
ORDER BY 1
DROP TABLE #Cubes
DROP TABLE #Splits
Here's some code to just return permutations up to 12 digits, which is a bit fun. It is far too slow to work as a problem solutions, however. It is very very slow.
WITH Permutations (c, p) AS
(
SELECT DISTINCT i1.c, CONCAT(i1.j, i2.j, i3.j, i4.j, i5.j, i6.j, i7.j, i8.j, i9.j, i10.j, i11.j, i12.j)
FROM #Splits i1
LEFT JOIN #Splits i2 ON i2.c = i1.c AND i2.i <> i1.i AND LEN(i1.c) > 1
LEFT JOIN #Splits i3 ON i3.c = i1.c AND i3.i NOT IN (i1.i, i2.i) AND LEN(i1.c) > 2
LEFT JOIN #Splits i4 ON i4.c = i1.c AND i4.i NOT IN (i1.i, i2.i, i3.i) AND LEN(i1.c) > 3
LEFT JOIN #Splits i5 ON i5.c = i1.c AND i5.i NOT IN (i1.i, i2.i, i3.i, i4.i) AND LEN(i1.c) > 4
LEFT JOIN #Splits i6 ON i6.c = i1.c AND i6.i NOT IN (i1.i, i2.i, i3.i, i4.i, i5.i) AND LEN(i1.c) > 5
LEFT JOIN #Splits i7 ON i7.c = i1.c AND i7.i NOT IN (i1.i, i2.i, i3.i, i4.i, i5.i, i6.i) AND LEN(i1.c) > 6
LEFT JOIN #Splits i8 ON i8.c = i1.c AND i8.i NOT IN (i1.i, i2.i, i3.i, i4.i, i5.i, i6.i, i7.i) AND LEN(i1.c) > 7
LEFT JOIN #Splits i9 ON i9.c = i1.c AND i9.i NOT IN (i1.i, i2.i, i3.i, i4.i, i5.i, i6.i, i7.i, i8.i) AND LEN(i1.c) > 8
LEFT JOIN #Splits i10 ON i10.c = i1.c AND i10.i NOT IN (i1.i, i2.i, i3.i, i4.i, i5.i, i6.i, i7.i, i8.i, i9.i) AND LEN(i1.c) > 9
LEFT JOIN #Splits i11 ON i11.c = i1.c AND i11.i NOT IN (i1.i, i2.i, i3.i, i4.i, i5.i, i6.i, i7.i, i8.i, i9.i, i10.i) AND LEN(i1.c) > 10
LEFT JOIN #Splits i12 ON i12.c = i1.c AND i12.i NOT IN (i1.i, i2.i, i3.i, i4.i, i5.i, i6.i, i7.i, i8.i, i9.i, i10.i, i11.i) AND LEN(i1.c) > 11
)
SELECT *
FROM Permutations
WHERE p IN (SELECT c FROM #Cubes)
-- Here's's a good test case that doesn't take forever.
-- This number has 3 cube permutations (and 20160 total permutations).
AND c = '41063625'