@Apass_Jack/

SubarraysOfLeastDifferentSums_cs110233

Java

No description

fork
loading
Files
  • Main.java
Main.java
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
import java.util.Arrays;
import java.util.Random;
import static java.lang.System.out;

public class Main {
    static int approximateLeastDifferenceOfSums(final int[] a, final int N) {
        final int n = a.length;

        final int s = Arrays.stream(a).sum();
        final double averageSum = 1.0 * s / N;
//        out.println("n=" + n + ", N=" + N + ", total=" + s + ", average=" + averageSum);

        boolean atLeast = true;

        int currentSum;
        int sumOfParts = 0;
        int max = -1;
        int min = s;

        int i = 0;
        int parts = 1;
        while (parts < N && i < n) {
            currentSum = 0;
            if (atLeast) {
                do {
                    currentSum += a[i++];
                } while (i < n && currentSum < averageSum);
            } else {
                do {
                    currentSum += a[i++];
                } while (i < n && currentSum + a[i] <= averageSum);
            }
            if (currentSum > max) max = currentSum;
            if (currentSum < min) min = currentSum;
//            out.println(averageSum + (atLeast ? " <= " : " >= ")
//                    + currentSum + ", (min,max)=(" + min + "," + max + ")");
            sumOfParts += currentSum;
            atLeast = (sumOfParts <= averageSum * parts);

            out.print(i + ", ");
            parts++;
        }

//        out.println(Arrays.toString(Arrays.copyOfRange(a, i, n)));
        currentSum = s - sumOfParts;
        if (currentSum > max) max = currentSum;
        if (currentSum < min) min = currentSum;
//        out.println(averageSum + (averageSum >= currentSum ? " >= " : " <= ")
//                + currentSum + ", (min,max)=(" + min + "," + max + ")");

        return max - min;
    }

    public static void main(String[] args) {
        approximateLeastDifferenceOfSums(new int[]{100,1,1,103,90}, 3);
        // small size so that repl.it won't block
        // for (int size = 30; size < 1000000; size = size * 2) {
        //     testRandom(size, 30);
        // }
    }

    static Random r = new Random();

    static void testRandom(int n, int N) {
        int[] numbers = new int[n];
        for (int i = 0; i < n; i++) {
            float f = r.nextFloat();
            if (f < 0.9) {
                numbers[i] = 1 + (int) (f * 10);
            } else if (f < 0.99) {
                numbers[i] = 1 + (int) ((f - 0.9) * 1000);
            } else {
                numbers[i] = 1 + (int) ((f - 0.99) * 100000);
            }
        }
        if (n < 300) {
            out.println(Arrays.toString(numbers));
        }
//        long start = System.currentTimeMillis();
        int delta = approximateLeastDifferenceOfSums(numbers, N);
        out.println("size=" + n + ", delta=" + delta);
//        long end = System.currentTimeMillis();
//        out.println(end - start);
    }
}