Creative thinking lab exercise

October 1, 2005 Andy

A stunning no-array-allowed lab exercise:

Write a program ListFractions.java to read in 2 positive integers n (1 < n <= 1000) and k from System.in, and pick the kth fraction from a list of fractions composed as follows:

A list of fractions is generated from the given n, where the denominator ranges from 2 to n, and the numerator is a positive integer smaller than the denominator, as shown below:
1/2, 1/3, 2/3, 1/4, 2/4, 3/4, …, (n-2)/n, (n-1)/n

The list is rearranged such that the fractions are in increasing magnitude, with duplicate values removed, retaining only the one in the simplest form among the duplicates.
For example, if n is 5, then the list in the required order is:
1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5
(2/4 is removed as it is equivalent to 1/2)
If n = 5 and k = 4, then the answer is 2/5 which is the 4th fraction in the list.

Well, if you dunno this sequence like me, bruteforce is the way to go. Yeah. I went by the bruteforce way. For those who know this Farey sequence, good for you too. You are simply looking for the easy way out instead of using your brain to code a algorithm, you rely on maths to help you solve it.

Well using the bruteforce method has got its cons, that is execution time. A sample bruteforce baseline has been set by the professor. His execution time is as follow.

$ java ListFractions
Enter n and k: 1000 2000
6/901
Elapsed time: 300.755 sec.

Well, below is my first and second try.

$ java ListFractions
Enter n and k: 1000 2000
6/901
Elapsed time: 220.124 sec.
$ javac ListFractions.java
$ java ListFractions
Enter n and k: 1000 2000
6/901
Elapsed time: 18.721 sec.

Aw, don’t mistake the 2nd one as using Maths approach. It is still bruteforce method. Just some tweaking and minus out unnecessary steps and the time taken to compute it drops 200 secs! How cool is that? I bet if i limit the range to search for, it would probably be 10s flat. Well, that’s another time.

Oh if you are interested, I bruteforced it by using the following approach.

let n = number of terms
let k = kth term of the series
set smallest to be 1 / n [first term]
loop thru from 1 / n to (n – 1) / n [practically generating the sequence]
look for the term just slightly greater than smallest
set smallest to be this new term
by doing this (k – 1) times, you can find the kth term as 1st term no need to find

Well hand was itchy so tried out Farey formula