Count contiguous sub-array whose sum is a perfect square

Question

I have to count the number of contiguous sub-arrays whose sum is a perfect square.

For instance, if we have an array:

number = [1,4,2,3,5]

Now the contiguous sub-arrays whose elements sum is a perfect square are:

[1] [4] [4,2,3]

Total count = 3

To solve this problem I took an array which stores the prefix sum and then I run two loops to get the answer:

int array[] = new int[n + 1];
int prefixSum[] = new int[n + 1];
int count = 0;
for (int index = 1; index <= n; index++) {
    array[index] = in.nextInt();
    prefixSum[index] = (prefixSum[index-1]+array[index]);
    count +=isPerfectSquare(prefixSum[index])?1:0;
}
for (int prev = 1; prev <= n; prev++) {
    for (int index = prev+1; index <= n; index++) {
        count += isPerfectSquare(prefixSum[index]-prefixSum[prev]) ? 1 : 0;
    }
}
System.out.println("count = " + count);

How can I improve this in terms of complexity?

Answer 1

You don't really use array[]. You store a value in array[index], and then immediately read the value back out, and then never use that value again. This results in unnecessary memory cycles.

    array[index] = in.nextInt();
    prefixSum[index] = (prefixSum[index-1]+array[index]);

You could replace this with a temporary variable, and remove the array.

    int element = in.nextInt();
    prefixSum[index] = prefixSum[index-1] + element;

As a minor efficiency boost, instead of adding the element to the prefixSum[index-1], which involves an array lookup (another memory cycle), you could keep the running total in a local variable.

int running_total = 0;
for (int index = 1; index <= n; index++) {
    int element = in.nextInt();
    running_total += element;
    prefixSum[index] = running_total;
    ...

---

You have two different ways of counting the sub-arrays that sum to a perfect square:

count += isPerfectSquare(prefixSum[index]                ) ? 1 : 0;
count += isPerfectSquare(prefixSum[index]-prefixSum[prev]) ? 1 : 0;

The first is used when you are counting from the beginning of the list, the second when you start by excluding one or more elements from the beginning.

You could make the first method look more like the second, by adding a subtraction of 0:

count += isPerfectSquare(prefixSum[index]-      0        ) ? 1 : 0;

By design (or is it by coincidence?), prefixSum[0] actually contains the value 0.

count += isPerfectSquare(prefixSum[index]-prefixSum[ 0  ]) ? 1 : 0;

So if your second loop started with for (int prev = 0; instead of for (int prev = 1;, you could remove your first counting statement completely.

---

Your outer nested loop runs one more time that necessary. It runs while prev <= n, where the inner loop starts at index = prev+1 and runs while index <= n. On the last iteration of the outer loop, prev == n, so index starts at index = n+1 and of course index <= n is immediately false, so the inner loop doesn't run at all, which makes this last iteration of the outer loop pointless. You could use prev < n as the loop condition.

---

The count += isPerfectSquare(...) ? 1 : 0; ternary operation isn't saving you much, and could be costing you some performance. The ternary operation is an if ... then ... else ... statement, and the else part is count += 0, which is a no-op. The following is clearer, and might even be faster.

        if (isPerfectSquare(...)) {
            count++;
        }

---

Improved code:

int prefixSum[] = new int[n + 1];
int count = 0;
int running_total = 0
for (int index = 1; index <= n; index++) {
    int element = in.nextInt();
    running_total += element;
    prefixSum[index] = running_total;
}
for (int prev = 0; prev < n; prev++) {
    for (int index = prev+1; index <= n; index++) {
        if (isPerfectSquare(prefixSum[index] - prefixSum[prev])) {
            count++;
        }
    }
}
System.out.println("count = " + count);