What About Tripartite or Quadripartite Numbers?
Another interesting task not directly related to the bipartite number problem is finding tripartite or quadripartite numbers. Well, you can handle that easily by using a table with the replicated numbers (table t3) and applying the same idea as you did for bipartite numbers (see
Listing 3):
Listing 3. How to Find Tripartite Numbers
SELECT (t3.sequence + t4.sequence + t5.sequence) AS [Tripartite Numbers]
FROM t3 CROSS JOIN t3 AS t4 CROSS JOIN t3 AS t5
WHERE LEFT(t3.sequence + t4.sequence + t5.sequence, 1) <> '0'
AND LEFT(t3.sequence, 1) <> LEFT(t4.sequence, 1)
AND LEFT(t3.sequence, 1) <> LEFT(t5.sequence, 1)
AND LEFT(t4.sequence, 1) <> LEFT(t5.sequence, 1)
ORDER BY 1
Result:
Tripartite Numbers
------------------------------------------
10000000002
100000000022
1000000000222
10000000002222
100000000022222
1000000000222222
10000000002222222
100000000022222222
1000000000222222222
10000000003
100000000033
1000000000333
10000000003333
. . . . . . . . . . .
. . . . . . . . . . .
99999999988888888866
999999999888888888666
9999999998888888886666
99999999988888888866666
999999999888888888666666
9999999998888888886666666
99999999988888888866666666
999999999888888888666666666
9999999998888888887
99999999988888888877
999999999888888888777
9999999998888888887777
99999999988888888877777
999999999888888888777777
9999999998888888887777777
99999999988888888877777777
999999999888888888777777777
(472392 row(s) affected)
Be careful, however, if you want to run a query for quadripartite numbers as in Listing 4:
Listing 4. How to Find Quadripartite Numbers
SELECT (t3.sequence + t4.sequence + t5.sequence + t6.sequence) AS [Quadripartite Numbers]
FROM t3 CROSS JOIN t3 AS t4 CROSS JOIN t3 AS t5 CROSS JOIN t3 AS t6
WHERE LEFT(t3.sequence + t4.sequence + t5.sequence + t6.sequence, 1) <> '0'
AND LEFT(t3.sequence, 1) <> LEFT(t4.sequence, 1)
AND LEFT(t3.sequence, 1) <> LEFT(t5.sequence, 1)
AND LEFT(t3.sequence, 1) <> LEFT(t6.sequence, 1)
AND LEFT(t4.sequence, 1) <> LEFT(t5.sequence, 1)
AND LEFT(t4.sequence, 1) <> LEFT(t6.sequence, 1)
AND LEFT(t5.sequence, 1) <> LEFT(t6.sequence, 1)
ORDER BY 1
This query is very heavy. If you want to test it anyway, you better decrease the number of rows in table t1. Run Listing 1 one more time, and insert numbers from 1 to 5 into the table t1.
Different SQL Server Version, Different Result
The quadripartite query from Listing 4 works fine for the five rows in table t1. It generates 2,835,000 quadripartite numbers but only in SQL Server 2000.
In SQL Server 2005, the same query for the same five rows in table t1 generates 2,196,003 quadripartite numbers and then fails with the following error:
"An error occurred while executing batch. Error message is: Couldn't replace text."
You can easily find the solution by going back to the original problem (see Listing 5):
Listing 5. Final Solution
-- sample input
DECLARE @input int
SET @input = 2005
-- min bipartite number, corresponding to the sample input
SELECT MIN(CAST(BipartiteNum as bigint)) AS minBipartiteNum
FROM
(SELECT (t3.sequence + t4.sequence) AS BipartiteNum
FROM t3 CROSS JOIN t3 AS t4
WHERE LEFT(t3.sequence + t4.sequence, 1) <> '0'
AND LEFT(t3.sequence, 1) <> LEFT(t4.sequence, 1)) T5
WHERE CAST(bipartiteNum AS bigint) % @input = 0
-- all bipartite numbers, corresponding to the sample input
SELECT CAST(BipartiteNum as bigint) BipartiteNum
FROM
(SELECT (t3.sequence + t4.sequence) AS BipartiteNum
FROM t3 CROSS JOIN t3 AS t4
WHERE LEFT(t3.sequence + t4.sequence, 1) <> '0'
AND LEFT(t3.sequence, 1) <> LEFT(t4.sequence, 1)) T5
WHERE CAST(bipartiteNum AS bigint) % @input = 0
Result:
minBipartiteNum
--------------------
222555
BipartiteNum
--------------------
222555
855555555
2222222555555555
Problem-Solving Outside the Box
Even though the ACM-ICPC 2006 World Finals contestants could use only Java, C/C++, or Pascal, it was very instructive to solve the problem in SQL—just one more example of how useful it is to see a problem from another point of view and use logical programming skills to solve it.
Previous Page
