Algorithm


Problem Name: Java Subarray

Problem Link: https://www.hackerrank.com/challenges/java-negative-subarray/problem?isFullScreen=true

In this HackerRank Functions in Java programming problem solution,

We define the following:

  • A subarray of an n-element array is an array composed from a contiguous block of the original array's elements. For example, if array = [1,2,3], then the subarrays are [1], [2], [3], [1,2], [2,3], [1,2,3]. Something like [1,3] would not be a subarray as it's not a contiguous subsection of the original array.
  • The sum of an array is the total sum of its elements.
  • An array's sum is negative if the total sum of its elements is negative.
  • An array's sum is positive if the total sum of its elements is positive.

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

Input Format

The first line contains a single integer, n, denoting the length of array A = [a0, a1,...,an-1].

The second line contains n space-separated integers describing each respective element, ai , in array A.

Constraints

  • 1 <= n <= 100
  • -10**4 <= ai <= 10**4

Output Format

Print the number of subarrays of A having negative sums.

Sample Input

5
1 -2 4 -5 1

Sample Output

9

 

 

 

 

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


import java.util.Scanner;

// A subarray must be contiguous. There are O(n^2) contiguous subarrays.

//  Time Complexity: O(n^2)
// Space Complexity: O(1)
public class Solution {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int size     = scan.nextInt();
        int[] array = new int[size];        
        for (int i = 0; i  <  size; i++) {
            array[i] = scan.nextInt();
        }
        scan.close();
        
        System.out.println(negativeSubarrays(array));
    }
    
    private static int negativeSubarrays(int[] array) {
        int count = 0;
        for (int i = 0; i  <  array.length; i++) {
            int sum = 0;
            for (int j = i; j  <  array.length; j++) {
                sum += array[j];
                if (sum  <  0) {
                    count++;
                }
            }
        }
        return count;
    }
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] African Cities in SQL solution in Hackerrank
Next
[Solved] Java Arraylist in Java solution in Hackerrank - Hacerrank solution Java