3
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't think it is possible to improve time complexity unless there are some additional constraints. For example if sum of all elements would be known to be much smaller than N*N, the amount of possible perfect squares would be P << N and you search for sub-arrays matching list of possible perfect squares. But it isn't any faster in generic case. \$\endgroup\$ – user158037 Sep 26 '18 at 9:28
1
\$\begingroup\$

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);
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ +1 for such a good explanation.Thanks for this @AJNeufeld. \$\endgroup\$ – Pmanglani Sep 26 '18 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.