-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathThreeLittlePigs.java
More file actions
50 lines (37 loc) · 1.5 KB
/
Copy pathThreeLittlePigs.java
File metadata and controls
50 lines (37 loc) · 1.5 KB
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
package gliderai;
import java.util.Arrays;
public class ThreeLittlePigs {
public static int countWaysToDivide(int[] arr) {
int n = arr.length;
if (n < 3) return 0; // Need at least 3 elements for a valid partition
int totalSum = Arrays.stream(arr).sum();
if (totalSum % 3 != 0) return 0; // If not divisible by 3, impossible to divide
int oneThird = totalSum / 3;
int twoThirds = 2 * oneThird;
int prefixSum = 0, countOneThird = 0, ways = 0;
for (int i = 0; i < n - 1; i++) { // Ensure at least one element remains for last partition
prefixSum += arr[i];
// When prefixSum reaches two-thirds, count previous one-third partitions
if (prefixSum == twoThirds) {
ways += countOneThird;
}
// Count the number of times one-third appears
if (prefixSum == oneThird) {
countOneThird++;
}
}
return ways;
}
public static void main(String[] args) {
int[][] testCases = {
{3, 3, 3, 3}, // Expected output: 1
{1, 1, 1}, // Expected output: 1
{1, 2, 3, 0, 3}, // Expected output: 1
{1, 1}, // Expected output: 0
{0, 0, 0, 0, 0} // Expected output: 10
};
for (int[] testCase : testCases) {
System.out.println("Output for " + Arrays.toString(testCase) + " : " + countWaysToDivide(testCase));
}
}
}