Given an array of integers, find and print its number of negative subarrays on a new line

Question

Given an array of N integers, find and print its number of negative subarrays (i.e sub arrays having negative summation) on a new line.

My code is taking \$\mathcal{O}(n^2)\$ time. How can I improve this?

import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int numberOfInts = sc.nextInt();
        int[] arr = new int[numberOfInts];

        for (int i = 0; i < numberOfInts; i++) {
            arr[i] = sc.nextInt();
        }
        int count = 0;
        for (int i = 0; i < numberOfInts - 2; i++) {
            int sum = arr[i];
            if (arr[i] < 0) {
                count++;
            }
            for (int j = i + 1; j < numberOfInts; j++) {
                sum = sum + arr[j];
                if (sum < 0) {
                    count++;
                }
            }
        }
        if (arr[numberOfInts - 1] < 0) {
            count++;
        }
        System.out.println(count);
    }
}

Roland Illig · Accepted Answer · 2017-10-06 06:24:48Z

Your code doesn't work for an empty array. Therefore it is conceptually wrong.

You should rewrite your code to be easily and automatically testable. This means to extract the interesting part of the program and separate it from the rest. In this case, the interesting part is the given an array, find. The code should therefore look like this:

static int countNegativeSubarrays(int... numbers) {
    int count = 0;
    // Your code here
    return count;
}

This method can be called easily from a test method:

static void runSelfTest() {
    if (countNegativeSubarrays() != 0)
        throw new AssertionError();
    if (countNegativeSubarrays(-1) != 1)
        throw new AssertionError();
    if (countNegativeSubarrays(-1, -1) != 3)
        throw new AssertionError();
    if (countNegativeSubarrays(-1, -1, -1) != 6)
        throw new AssertionError();
    if (countNegativeSubarrays(1, -1, -2, 5) != 4)
        throw new AssertionError();
    // Add more test cases here
}

In your main method you should run this self-test before accepting any input from the user.

Stack Exchange Network

Given an array of integers, find and print its number of negative subarrays on a new line

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Given an array of integers, find and print its number of negative subarrays on a new line

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions