Repeatedly partitioning an array equally as far as possible

I solved HackerRank Nikita and the Game. The implementation is correct as program passes all test cases.

Nikita just came up with a new array game. The rules are as follows:

• Initially, there is an array, A, containing N integers (1 ≤ N ≤ 109), with 0 ≤ Ai ≤ 109.

• In each move, Nikita must partition the array into 2 non-empty parts such that the sum of the elements in the left partition is equal to the sum of the elements in the right partition. If Nikita can make such a move, she gets 1 point; otherwise, the game ends.

• After each successful move, Nikita discards either the left partition or the right partition and continues playing by using the remaining partition as array A.

Nikita loves this game and wants your help getting the best score possible. Given A, can you find and print the maximum number of points she can score?

import java.io.*;
import java.util.*;

public class NikitaAndTheGame
{

public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int cases=sc.nextInt();
for(int i=0;i<cases;i++)
{
int size=sc.nextInt();
int[] array=new int[size];

for(int j=0;j<size;j++)
{
array[j]=sc.nextInt();
}

System.out.println(splitPossible(array,0,size-1));

}
}
public static int splitPossible(int[] array,int start,int end)
//a recursive fuction that returns 1 if equal sum split possible otherwise returns 0
{
int size=end-start+1;
int sum=0;
int count=0;
if(sumOfArray(array,0,array.length-1)==0&&start==0&&end==array.length-1) //handles the case when all elements of array are 0.

{
return array.length-1;
}
if(size==0)
{
return 0;
}
for(int i=0;i<size;i++)
{
if(sumOfArray(array,start,start+i)!=sumOfArray(array,start+i+1,end))
{
continue;
}
else
{
count+=1;
return count+Math.max(splitPossible(array,start,start+i),splitPossible(array,start+i+1,end));
}
}

return count;
}
public static int sumOfArray(int[] array,int start,int end)
//returns sum of array from start to end.
{
int sum=0;
for(int j=start;j<=end;j++)
{
sum+=array[j];
}
return sum;
}
}


I am new to recursion, so any input in designing of recursive method/assigning or simplifying variables/simpler coding styles during recursion are welcomed.

• Has the problem statement changed? The limits don't match; HackerRank has N<=2^14 and the word "contiguous" is missing here. Also, does this version genuinely pass the tests with max size data? – JollyJoker Nov 8 '16 at 13:48

The implementation of the algorithm, using a helper recursive method, is very clear. It is easy to see what the code is doing:

• There are 2 base cases: there are only 0s, in which case the size of the array is the score, and the size is zero, in which case the score is 0.
• Then, for all possible sizes, we keep the maximum of the score of the left array versus the right array when they have equal sum, adding 1.

There are simplifications possible, and improvements in terms of style and namings.

Namings

The first point to consider is naming: splitPossible is a terrible name for this method. It doesn't convey what it's doing. Rename it to getMaxScore, since this is what it does: gets the maximum score for the given array in the given bounds.

Also, consider "hiding" the recursive implementation inside a new method by creating a method passing the initial values:

public static int getMaxScore(int[] array) {
return getMaxScore(array, 0, array.length - 1);
}

private static int getMaxScore(int[] array, int start, int end) {
// rest of code
}


This way, the caller just needs to invoke getMaxScore(array), without worrying about the initial value of the recursive algorithm; and it gives you the possibility to update the code in the future (to an iterative method for example) without changing the calling code.

Style

You should always reformat your code in order to have proper indentation. Right now, it isn't the case and makes the code harder to read for no reason.

int sum = 0;


is unused in the program, so you should remove it.

if (sumOfArray(array, start, start + i) != sumOfArray(array, start + i + 1, end)) {
continue;
} else {
count += 1;
return count + Math.max(getMaxScore(array, start, start + i), getMaxScore(array, start + i + 1, end));
}


is the logic for the recursive calls. In this case, there is no need to use a continue statement: those can sometimes help understanding the logic when there would be a lot of code in the else branch. They introduce a sort of early-return inside the for loop. But in this case, it clutters up a bit, and you can simply have:

if (sumOfArray(array, start, start + i) == sumOfArray(array, start + i + 1, end)) {
count += 1;
return count + Math.max(getMaxScore(array, start, start + i), getMaxScore(array, start + i + 1, end));
}


A couple of more comments here: count += 1; is more generally written count++ (or ++count), but in fact, there is no need for this as you can just add 1 to the result of the next line:

return 1 + count + Math.max(getMaxScore(array, start, start + i), getMaxScore(array, start + i + 1, end));


Arguably, this line is starting to become a bit crowded, so it is possible to store the two intermediate recursive results in temporary variables:

int leftScore = getMaxScore(array, start, start + i);
int rightScore = getMaxScore(array, start + i + 1, end);
return 1 + count + Math.max(leftScore, rightScore);


Improvements

You have an early return in case the size is 0, to return 0. While that can make the code easier to follow in certain situations, in this case, it's not needed at the rest of the code handles size = 0 just fine. Actually, the for loop is not entered, and we directly return the count, which is 0. Consider removing this special case (it also doesn't lead to performance improvements).

But why is there a count variable in the first place? It's initialized to 0, and in fact never changes. It's actually really unneeded: when making the recursive call, the total score is always the maximum score of the left and right split, plus 1. You can safely remove this count variable.

The first if, in case the array only contains 0, can be written more simply as well: start == 0 && end == array.length - 1 is equivalent to size == array.length.

The recursive method now looks like:

public static int getMaxScore(int[] array, int start, int end) {
int size = end - start + 1;
if (sumOfArray(array, 0, array.length - 1) == 0 && size == array.length) {
return array.length - 1;
}
for (int i = 0; i < size; i++) {
if (sumOfArray(array, start, start + i) == sumOfArray(array, start + i + 1, end)) {
int leftScore = getMaxScore(array, start, start + i);
int rightScore = getMaxScore(array, start + i + 1, end);
return 1 + Math.max(leftScore, rightScore);
}
}
return 0;
}


Finally, something can be done to simplify this first early-return. When all the elements in the array are 0, the recursive calls inside the for loop handle the case fine as well: they will increment the count by 1 each time, finally ending up with array.length - 1. But we can't get total rid of it: the way the algorithm is build, splitting each array into smaller chunks, the special case is when size == 1, and in this case, it is impossible to split it evenly, so the answer is 0. So we could have

if (size == 1) {
return 0;
}


which avoids traversing the array entirely.

Further improvements

It might sound a bit strange to you, as it probably is to new developers, but a lot of APIs, for all programming languages, very often deal with ranges in an open-half manner: when asked for something in the range from start to end, it will generally be implied start inclusive to end exclusive (like Python slice, C++ APIs, and in Java, look at Random.nextInt, IntStream.range, List.subList or String.substring). The current code implies that the end is inclusive, which, actually, makes it that bit harder to follow for those accostumed to those practices. And switching to an exclusive end will make the code even easier:

// start inclusive, end exclusive
public static int getMaxScore(int[] array, int start, int end) {
for (int i = 1; i < end - start; i++) {
int split = start + i;
if (sumOfArray(array, start, split) == sumOfArray(array, split, end)) {
return 1 + Math.max(getMaxScore(array, start, split), getMaxScore(array, split, end));
}
}
return 0;
}

// start inclusive, end exclusive
public static int sumOfArray(int[] array, int start, int end) {
int sum = 0;
for (int j = start; j < end; j++) {
sum += array[j];
}
return sum;
}

• There is no need to have special cases for a size of 0 or 1; the code handles them already.
• There is a clear split index, which corresponds to where the left and right arrays are split.

All the test cases still pass after making those changes.

I'd consider changing the basic algorithm you use. As it stands, it'll probably work for small test cases, but exceed any reasonable time limit if the array is even close to the stated limit of $10^9$ elements.

As it stands right now, it repeats a lot of computation quite unnecessarily. The result is that the algorithm has a complexity of something like $O(N^4 log N)$ (a single partition step takes $O(N^2)$, and you repeat this something like $O(N^2 log N)$ times)1.

Right now, you iterate over a collection and try different partition points, completely re-computing the sum for each partition at each step. This is what leads to the partitioning being $O(N^2)$.

You don't need to do that though. Let's think of the partitions as "left" and "right"--the left is those toward the beginning of the collection, and the right those toward the end.

We can start with the first element in the left partition, and the remainder in the right. Assuming those aren't equal, we need to try the next position--but to do what we don't need (or want!) to re-compute the sum of each partition from the beginning. Rather, we're just moving one element from right to left. We can do that by subtracting it from the sum of the right partition and adding it to the sum of the left partition:

long left = array[0];
long right = sumOfArray(array, 1, end);

for(int i=0;i<size;i++)
{
if (left == right)
{
return count + 1 + Math.max(splitPossible(array,start,start+i),splitPossible(array,start+i+1,end);
}
else
{
left += array[i];
right -= array[i];
}


Personally, however, I'd at least consider reversing things: instead of "step through the array, and return in the middle of the loop if we find a balance point, I'd think more like: "find a balance point, then if one exists, find which sub-array gives the higher score:

while (left != right && i < end) {
left += array[i];
right -= array[i];
i++;
}
if (left != right)
return 0;
return count + 1 + Math.max(findPartition(array, 0, i), findPartition(array, i, end);


Personally, I find this a little cleaner, but it's at least arguably a matter of taste.

Either way, just moving each element instead of re-computing the sum every time reduces the task of generating the next partition from being $O(N)$ to $O(1)$. Since we do that $O(N)$ times to find a valid partitioning, we've reduced the partitioning task from $O(N^2)$ to $O(N)$.

Having found that partition, you then use recursion to find which of the child partitions will maximize the score.

One other point worth noting: it is possible that at any given step, there could be multiple partitions that work. In particular, after you find a partition that works, if it's followed by one or more zeros (allowed by the requirement: $0 ≤ A_i ≤ 10^9$). Each partition must be non-empty, but it's sum isn't required to be non-zero, so a partition could reach a point at which you have (for example) only two zeros, which can still be partitioned to get two more partitions with equal sums (zero for each).

So, if a legal partition point is followed by one or more zeros, you can have more allowable partition points, and even though they all have identical sums, they may not have identical scores).

One more point: although it's unlikely to arise in test cases, if you get a large array (at or close to the $10^9$ limit) the sum of an array can exceed the range of an int. You just about need to switch to a long (which, at least if memory serves, Java guarantees has a range up to $2^{63}-1$--more than enough to sum an array of $10^9$ elements each with the value $10^9$.

1. I'm not sure I've figured the number of repetitions precisely correctly, but it is pretty clear that the partitioning step is $O(N^2)$, and that's what we're changing.

• If the array has no equlibrium point where left == right, you will iterate till i == end. But you don't have to (unless the last item of the array is greater than or equal to the sum of all preceding items). Take into account that array items are non-negative, hence the difference right-left can't increase when i grows. So you can make weightDiff = sumOfArray(...) and iterate weightDiff -= 2*array[i] while weightDiff is positive (and i<end). Then recur if weightDiff became zero or return zero otherwise. – CiaPan Aug 16 '17 at 11:54

General guidelines:

• Formatting (Indentation, spacing) for better readability.

Algorithm review:

• size == 0 => end-start+1 = 0 => end = start - 1 Its better to check end < start which adds more readbility.

• sumOfArray(array,0,array.length-1). This is a constant calculation with same parameters that happens over every recursive call. Avoid it as the output would not change.

• if(sumOfArray(array,0,array.length-1)==0&&start==0&&end==array.length-1) This check holds true only for the first call but is checked for every recursive call. You could have a splitArrayUtil that takes care of the edge conditions in the initial go and then calls splitPossible where only the arguments matter with no invariant calculation.

• For an array of size 1, their is undue calculation with no check for indexes moving outside the array's bounds.

I got an idea for an O(n) solution by finding partial sums that are valid 1/2, 1/4, 3/4 etc. parts of the full sum. I kinda despaired for a while when I realized zeroes give different partitions, but after giving up and reading comments on HackerRank, I found a mention of only the case where all are zeroes mattering. This passes all the test on HackerRank and should work fine (fast) with very large inputs.

I go through all the sums from start, checking if they are divisible by the (product of) all odd factors of the total sum. I store them in a "tree", a list of lists where the "height" in the tree, the index in the main list, depends on how many times the number is divisible by two, or how many zeroes there are at the end of the binary representation. Finally just loop through what I have and see which numbers on the next level would be valid children of the numbers in the current level. For example, if there's a 128, valid children would be 64 and 192.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static long sum(int[] arr) {
long sum = 0;
for(int i : arr) {
sum += i;
}
return sum;
}

public static List<List<Long>> getTree(List<Integer> arr, long oddFactors, int twos) {
List<List<Long>> tree = new ArrayList<List<Long>>();
for(int i=0; i<twos; ++i) {
}
long partialSum = 0;
for(int i=0; i<arr.size()-1; ++i) {
partialSum += arr.get(i);
if(partialSum % oddFactors == 0) {
long evenSum = partialSum / oddFactors;
int height = twos - Long.numberOfTrailingZeros(evenSum) - 1;
}
}
return tree;
}

public static int populatedHeight(List<List<Long>> tree) {
if(tree.isEmpty() || tree.get(0).isEmpty()) {
return 0;
}
int populated = 1;
for(int i=0; i<tree.size()-1; ++i) {
List<Long> children = new ArrayList<Long>();
for(long j : tree.get(i)) {
long offset = Long.lowestOneBit(j) / 2;
}
List<Long> realChildren = intersection(children, tree.get(i+1));
if(realChildren.isEmpty()) {
break;
} else {
tree.set(i+1, realChildren);
++populated;
}
}
return populated;
}

public static List<Long> intersection(List<Long> a, List<Long> b) {
List<Long> intersection = new ArrayList<Long>();
int i=0, j=0;
while(i < a.size() && j < b.size()) {
if(a.get(i) < b.get(j)) {
++i;
} else if(a.get(i) > b.get(j)) {
++j;
} else {
++i;
++j;
}
}
return intersection;
}

public static void handleCase(int[] arr) {
long sum = sum(arr);
if(sum == 0) {
System.out.println(arr.length-1);
return;
}
List<Integer> nonZero = new ArrayList<Integer>();
for(int i : arr) {
if(i != 0) {
}
}
long twoFactors = Long.lowestOneBit(sum);
int twos = Long.numberOfTrailingZeros(sum);
long oddFactors = sum / twoFactors;
System.out.println(populatedHeight(getTree(nonZero, oddFactors, twos)));
}

public static void main(String[] args) {

Scanner sc=new Scanner(System.in);
int cases=sc.nextInt();
for(int i=0;i<cases;i++) {
int size=sc.nextInt();
int[] array=new int[size];

for(int j=0;j<size;j++) {
array[j]=sc.nextInt();
}
handleCase(array);
}
sc.close();
}
}