-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathThreeLittlePigs1.java
More file actions
86 lines (64 loc) · 2.73 KB
/
Copy pathThreeLittlePigs1.java
File metadata and controls
86 lines (64 loc) · 2.73 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
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
package gliderai;
public class ThreeLittlePigs1 {
// public static int countWaysToDivide(int[] arr) {
// int n = arr.length;
// if (n < 3) return 0; // Need at least 3 elements to divide
// int totalSum = 0;
// for (int num : arr) totalSum += num;
// if (totalSum % 3 != 0) return 0; // Cannot split into three equal parts
// int oneThird = totalSum / 3;
// int twoThirds = 2 * oneThird;
// int ways = 0;
// int prefixSum = 0;
// int countOneThird = 0;
// for (int i = 0; i < n - 1; i++) { // Ensure at least one element remains for last partition
// prefixSum += arr[i];
// if (prefixSum == twoThirds) {
// ways += countOneThird; // Valid second partition found
// }
// if (prefixSum == oneThird) {
// countOneThird++; // Count occurrences of one-third partition
// }
// }
// return ways;
// }
public static int countWaysToDivide(int[] arr) {
int n = arr.length;
if (n < 3) return 0; // Need at least 3 elements
int totalSum = 0;
for (int num : arr) totalSum += num;
if (totalSum % 3 != 0) return 0; // Cannot split into three equal parts
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 is equal to 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[] arr1 = {-2, 4, 2, 1, 1}; // Example input
System.out.println(countWaysToDivide(arr1)); // Output: 1
int[] arr2 = {4, 3}; // Example input with only 2 elements
System.out.println(countWaysToDivide(arr2)); // Output: 0
System.out.println("***"); // More test cases
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 " + java.util.Arrays.toString(testCase) + " : " + countWaysToDivide(testCase));
}
}
}