Hackerrank Java Subarray Solution

Hackerrank Java Subarray Solution

We define the following:

  • A subarray of an -element array is an array composed from a contiguous block of the original array's elements. For example, if , then the subarrays are , , , , , and . Something like  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  integers, find and print its number of negative subarrays on a new line.

Input Format

The first line contains a single integer, , denoting the length of array .
The second line contains  space-separated integers describing each respective element, , in array .

Constraints

Output Format

Print the number of subarrays of  having negative sums.

Sample Input

5
1 -2 4 -5 1

Sample Output

9

Explanation

There are nine negative subarrays of :

Thus, we print  on a new line.

Solution in java8

Approach 1.

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

public class Solution {

    public static void main(String[] args) {
    	Scanner in = new Scanner(System.in);
    	int n = in.nextInt();
    	int count =0;
    	int arr[] = new int[n];
    	for(int i=0; i<n; i++) arr[i] = in.nextInt();
    	for(int i=0; i<n; i++) {
    		int sum = 0;
    		for (int j=i; j<n; j++) {
    			sum = arr[j]+sum;
    			if (sum<0) count++;
    		}
    	}
    	System.out.println(count);
    }
}

Approach 2.

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

public class Solution {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] numbers = new int[n];
        // populate the array
        for(int i = 0; i<n;i++){
            numbers[i] = scan.nextInt();
        }
        
        int total = 0;
        int sum;
        // For each starting position
        for(int i = 0; i < n; i++){
            sum = 0;
            for(int j = i; j<n; j++){
                sum += numbers[j];
                if(sum < 0){
                    total++;
                }
            }
        }
        System.out.println(total);
           
    }
}

Approach 3.

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

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = 0;
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        
         
        int l=1;
        while (n - l >= 0) {
			for (int i = 0; i < n; i++) {
				int[] arrnew = Arrays.copyOfRange(arr, i, i + l);
				if (i + l <= n) {
					int sum = 0;
					for (int j = 0; j < arrnew.length; j++) {
						sum += arrnew[j];
					}
					if (sum < 0)
						count++;
				}
			}
			l++;
		}
        System.out.println(count);
    }
}

Subscribe to The Poor Coder | Algorithm Solutions

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.
[email protected]
Subscribe