rogramming is not only remembering Java classes or the numerous utilities that appear almost every day. It is also the ideas in Donald E. Knuth’s “The Art of Computer Programming” and Dr. Ted Codd‘s SQL, fundamental principles from which .NET libraries and Java classes are derived. While new technologies, methods, and techniques are of course important, developing and honing your logical programming skills are perhaps more vital.

While professional programmers’ day-to-day work often challenges these skills, the ACM International Collegiate Programming Contest (ACM-ICPC) puts young programmers’ skills to the test. It is the world’s largest collegiate programming competition, but you don’t have to be a university student to learn something from it. This article presents a SQL solution to one of the problems from the ACM-ICPC 2006 World Finals, the gist of which can apply to real-world problem solving.

The Bipartite Numbers Problem

Problem D from the ACM-ICPC 2006 World Finals was “Bipartite Numbers”. A bipartite number is any positive integer that contains exactly two distinct decimal digits, s and t, such that s is not 0 and all occurrences of s precede all occurrences of t. For example, 44,444,411 is bipartite (s is 4 and t is 1), so are 41, 10,000,000, and 5,555,556. However, neither 4,444,114 nor 44,444 is bipartite.

Notice that the large bipartite number 88,888,888,888,800,000 can be neatly described as 12 8’s followed by 5 0’s. You can express any bipartite number using four numbers: m, s, n, and t. The numbers s and t are the leading and trailing digits as described above: m is the number of times the digit s appears in the bipartite number, and n is the number of times the digit t appears.

Problem D requires you to write a program that takes a positive integer as input and displays the corresponding smallest bipartite number that is greater than and a multiple of the input integer. You need to find the solution for the input integer in the range 1 … 99,999. The following is sample input with corresponding output:

Sample Input     Output for the Sample Input
-----------------------------------------------------
125                     500
17502                 77778888
2005                   222555

One possible solution for this problem would be repeated multiplication, where the multiplicand is always the same and equal to the input number, and the multiplier is changed dynamically to become 2, 3, 4, 5, 6…, and so on. You’d need to check each result to see if a product is a bipartite number.

I wouldn’t bother with that solution because it would be inefficient, especially if you are asked to find not just the smallest bipartite number, but also all possible bipartite numbers in the specified range. I searched for more efficient solution and found it… in SQL.

The Answer Lies in SQL

If you think about it, bipartite numbers are nothing more than two-digit numbers from 10 to 98, excluding cases where the first and second digits are equal (11, 22, 33, 44, 55, 66, 77, 88, 99). The pool of two-digit numbers can be extended by the digit’s replication. Theoretically, you can replicate each digit any number of times, but in real world, the degree of replication (number of replicated digits) will be limited by data type. This leads to two interesting tasks for solving the problem:

1. Generating a set of replicated digits from 0 to 9
2. Finding all bipartite numbers in the specified range

The solution in Listing 1 accomplishes the first task:

Listing 1. Generate a Set of Replicated Digits from 0 to 9SET NOCOUNT ONIF  EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'dbo.t1')               AND type in (N'U'))DROP TABLE dbo.t1IF  EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'dbo.t2')               AND type in (N'U'))DROP TABLE dbo.t2IF  EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'dbo.t3')               AND type in (N'U'))DROP TABLE dbo.t3CREATE TABLE t1(c1 int);INSERT INTO t1SELECT 1 AS C1UNION ALLSELECT 2UNION ALLSELECT 3UNION ALLSELECT 4UNION ALLSELECT 5UNION ALLSELECT 6UNION ALLSELECT 7UNION ALLSELECT 8UNION ALLSELECT 9;CREATE TABLE t2(c1 VARCHAR(20));INSERT INTO t2SELECT '0' AS c1UNION ALLSELECT '1'UNION ALLSELECT '2'UNION ALLSELECT '3'UNION ALLSELECT '4'UNION ALLSELECT '5'UNION ALLSELECT '6'UNION ALLSELECT '7'UNION ALLSELECT '8'UNION ALLSELECT '9';SELECT REPLICATE(t2.c1, t1.c1) sequenceINTO t3FROM t1 CROSS JOIN t2ORDER BY 1SELECT * FROM t3Reulst:Sequence---------000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111. . . . . . .. . . . . . .. . . . . . .. . . . . . .888888888888888888888888888888888888888888888999999999999999999999999999999999999999999999(90 row(s) affected)

The maximum number of replicated digits in my example is 9 (equal to the biggest number inserted into table t1). If you want to replicate more digits, then insert more numbers (10, 11, and so on) into table t1.

Now, you can proceed and find all possible combinations of two distinct rows in table t3. You can do this using cross-join by joining table t3 to itself in a self-join (see Listing 2):

Listing 2. How to Find Bipartite NumbersSELECT  (t3.sequence + t4.sequence) AS [Bipartite Numbers]   FROM t3 CROSS JOIN t3 AS t4   WHERE LEFT(t3.sequence + t4.sequence, 1) <> '0'   AND LEFT(t3.sequence, 1) <> LEFT(t4.sequence, 1)   ORDER BY 1Result:Bipartite Numbers------------------101001000100001000001000000100000001000000001000000000110110011000110000. . . . . . . . . . . . . . . . 1111111000000011111110000000011111110000000001111111101111111100111111110001111111100001111111100000. . . . . . . .. . . . . . . . 111111111999911111111199999111111111999999111111111999999911111111199999999111111111999999999. . . . . . . . . . . . . . . . . . . . 99999999988888999999999888888999999999888888899999999988888888999999999888888888(6561 row(s) affected)

As you can see, two predicates in the WHERE clause filter the cases where the number in the result set starts from zero and where the starting digits in the numbers that need to be combined are equal.

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 NumbersSELECT (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 1Result:Tripartite Numbers------------------------------------------10000000002100000000022100000000022210000000002222100000000022222100000000022222210000000002222222100000000022222222100000000022222222210000000003100000000033100000000033310000000003333. . . . . . . . . . .. . . . . . . . . . .99999999988888888866999999999888888888666999999999888888888666699999999988888888866666999999999888888888666666999999999888888888666666699999999988888888866666666999999999888888888666666666999999999888888888799999999988888888877999999999888888888777999999999888888888777799999999988888888877777999999999888888888777777999999999888888888777777799999999988888888877777777999999999888888888777777777(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 NumbersSELECT (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 inputDECLARE @input intSET @input = 2005 -- min bipartite number, corresponding to the sample inputSELECT 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 inputSELECT 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 = 0Result:minBipartiteNum--------------------222555BipartiteNum--------------------2225558555555552222222555555555

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.