Java BigDecimal | HackerRank Solution

Java BigDecimal on HackerRank looks like a plain sorting task, but it hides two requirements that catch a lot of people. You must sort decimal numbers by their real value while printing them exactly as they were typed, so ".12" stays ".12". And when two numbers are equal in value, like "0.12" and ".12", they must keep their original input order. That second rule is called stability, and the old solution on this page broke it.

Solving it properly teaches you how BigDecimal compares numbers, why equals and compareTo disagree for it, and why you should reach for the library sort instead of writing your own.

Problem

You get n strings, each holding a real number. Some may have leading zeros, no digit before the decimal point, or a minus sign. Rearrange them in descending order of numeric value. Print every number exactly as it appeared in the input. If two numbers are equal in value, the one that came first in the input must also come first in the output.

On HackerRank, the input reading and printing are locked. You only fill in the part that reorders the array s. The locked code makes s a little longer than n (with empty slots at the end), which matters, as you will see.

Input format: the first line has n. Each of the next n lines has one number.

Output format: the numbers in the new order, one per line.

Constraints: 1 <= n <= 200, and each number has at most 300 digits.

Input
9
-100
50
0
56.6
90
0.12
.12
02.34
000.000

Output
90
56.6
50
02.34
0.12
.12
0
000.000
-100

Approach

300 digits rules out double. A double holds only about 15 to 17 significant digits, so two different long numbers could look equal. BigDecimal stores the exact decimal value, and new BigDecimal(".12") and new BigDecimal("02.34") both parse fine.

1. Keep the original strings in the array. Never replace them with converted values, or you lose the original formatting.
2. Sort the strings with a comparator that converts each one to BigDecimal and compares with compareTo, in reverse for descending order.
3. Use Arrays.sort for objects. It is guaranteed stable (it uses TimSort, a merge sort variant), so equal values keep their input order without any extra work.
4. Sort only the range from 0 to n, so the empty slots at the end are never touched.

Dry run on the tricky part: "0.12" (input position 6) and ".12" (position 7) both equal 0.12, so compareTo returns 0 for them. A stable sort leaves them in input order: "0.12", then ".12". The same happens for "0" and "000.000". That is exactly the expected output.

Solution in Java

The older solution here used selection sort: find the largest remaining value and swap it into place. Swapping is the problem. It can jump an element over an equal one and change their order. On the input 1, 1.0, 2 the old code prints 2, 1.0, 1, but the correct answer is 2, 1, 1.0. It happened to pass the sample, but it is wrong in general.

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next();          // keep the original text untouched
        }

        // Compare by numeric value, largest first.
        // Arrays.sort on objects is a stable merge sort (TimSort), so
        // equal values like ".12" and "0.12" keep their input order.
        Arrays.sort(s, 0, n,
            Comparator.comparing((String x) -> new BigDecimal(x)).reversed());

        for (int i = 0; i < n; i++) {
            System.out.println(s[i]);
        }
    }
}

In the HackerRank editor, keep their locked code and only put the Arrays.sort line (with the imports) in the editable part. Their array is declared with extra length, which is why sorting the range 0 to n matters; sorting the whole array would hit null entries and throw a NullPointerException.

Edge cases I ran: 1, 1.0, 2 gives 2, 1, 1.0 (stable, unlike the old code). Negatives -0.5, -.5, -0.50, -1 keep the three equal values in input order and put -1 last. Two 31-digit numbers that differ only in the last decimal place are ordered correctly, which a double could not guarantee.

Output

90
56.6
50
02.34
0.12
.12
0
000.000
-100

Complexity

Time: O(n log n) comparisons. Each comparison parses two strings of up to 300 digits, so it costs O(d) where d is the number of digits. With n at most 200 this is tiny. If n were large, you would convert each string once and sort pairs of (value, string) instead of parsing inside the comparator.

Space: O(n) for the merge sort's temporary storage.

Common mistakes

• Using equals to test equal values. For BigDecimal, equals also compares scale, so 0.5 and 0.50 are not "equal". Use compareTo(...) == 0.
• Printing the BigDecimal instead of the string. new BigDecimal(".12").toString() prints "0.12", which changes the format the problem asks you to keep.
• Writing your own unstable sort. Selection sort and quicksort are not stable. Bubble sort and insertion sort are stable but slow. The library sort for objects is stable and fast.
• Comparing with == 1. The old code checked compareTo(...) == 1. It works for BigDecimal, but the general contract only promises a positive number, so > 0 is the safe habit.

Related: Java Primality Test uses BigInteger, the integer sibling of BigDecimal, and Day 20: Sorting covers sorting from scratch.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More HackerRank solutions All coding problems MCQ practice