Problem

You are given an array of non-negative integers, where different integers may have different numbers

of digits, but the total number of digits over all the integers in the array is n. Show how to sort the

array in O(n) time1.

1 The algorithm you are expected to implement, strictly speaking, runs in O(b · n) time, where b is the base for counting

sort. However, since we set b = 128, b is a constant and the runtime is therefore O(n).

To implement this problem, we represent a single integer as array of bytes. Each byte represents a digit

(base 128). The byte with index 0 in the array represents the least significant byte. That is, if A has

length 3, A[0] = 6, A[1] = 7, and A[2] = 8, then A represents the number 6·1280+7·1281+8·1282.

Implementation

You are given a file Lab3.java. The file contains a class Lab3

with a function problem. Implement your solutions in this function. Do not make any changes

outside of that function (e. g. by adding helper functions); such changes will be undone. Do

not output anything to the terminal.

The program already implemented in the file Lab3.java randomly generates test cases. The seed of

the random number generator is set to ensure the same test cases whenever to program is executed.

Note that the purpose of the tests is for you to avoid major mistakes. Passing all given tests does

not imply that your algorithm is correct, especially that is has the expected runtime.

0 comments