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
, 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
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.