Realize Largest Remainder Method Using Java

algorithm

Realize Largest Remainder Method Using Java

Introduction

pie

As shown in the above picture, sometimes we find that the total value in a pie chart is not equal to 100%. By using largest remainder method, we can address this problem.

In largest remainder method, each element is first allocated a percentage value equal to their integer. The elements are then ranked on the basis of the fractional remainders, and the elements with the largest remainders are each allocated one additional percentage until all the percentages have been allocated.

For example, we have an array {3, 4, 5}, and the sum of the array elements is 12.

3/12 * 100 = 25, and the remainder is 0.
4/12 * 100 = 33.33, and the remainder is 0.33.
5/12 * 100 = 41.67, and the remainder is 0.67.

According to the integer part, we first allocate a percentage value of 25 to 3, a percentage value of 33 to 4, and a percentage value of 41 to 5. Now we have allocated 25+33+41=99 percentage. For the last 1 percent, we allocate it to 5 because its remainder is larger than 3 and 4. Therefore we have [25, 33, 42] for value 3, 4 and 5.

Java Implement of Largest Remainder Method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import java.util.Arrays;

/**
 * @author Leslie Tang
 * @version 2019/11/27
 */
public class LargestRemainderMethod {

    // Get the percentage value of all the elements in an array,
    // which is based on the largest remainder method.
    public static int[] getPercentageValue(int[] array) {
        if (array.length == 0) {
            throw new IllegalArgumentException();
        }

        int sum = getSum(array);
        if (sum == 0) {
            System.out.println("Cannot compute percentage value of the array.");
        }


        int[] result = new int[array.length];

        // Each element is first allocated a percentage value equal
        // to their integer.
        for (int i = 0; i < array.length; i++) {
            result[i] = array[i] * 100 / sum;
        }


        int currentSumOfPercentage = 0;
        for (int i : result) {
            currentSumOfPercentage += i;
        }

        double[] remainder = new double[array.length];
        for (int i = 0; i < result.length; i++) {
            remainder[i] = (double) array[i] / sum * 100 - result[i];
        }

        // The elements are then ranked on the basis of the fractional remainders,
        // and the elements with the largest remainders are each allocated one
        // additional percentage until all the percentages have been allocated.
        while (currentSumOfPercentage < 100) {
            int index = getMax(remainder);
            result[index]++;
            remainder[index] = 0;
            currentSumOfPercentage++;
        }

        return result;

    }

    // Get the sum of all the elements in an array.
    public static int getSum(int[] array) {
        int sum = 0;
        for (int i : array) {
            sum += i;
        }
        return sum;
    }

    // Get the index of the maximal element in an array.
    public static int getMax(double[] array) {
        int maxIndex = 0;
        double maxValue = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > maxValue) {
                maxValue = array[i];
                maxIndex = i;
            }
        }

        return maxIndex;
    }

    // main method to test the result
    public static void main(String[] args) {
        int[] array = {3, 3, 4};
        int[] result = getPercentageValue(array);
        System.out.println(Arrays.toString(result));// output: [30, 30, 40]

        System.out.println("----------------------");

        System.out.println(Arrays.toString(getPercentageValue(new int[]{3,4,5})));// output: [25, 33, 42]

    }
}