LinkedIn

Subarray Sum

Given a array of integers, find out the sum of all subarrays

Ex:[1,2,3] -> [1], [2], [3], [1,2], [2,3], [1,2,3]

sum = 20

• Every element arr[i] appears in two types of subsets:

  • In sybarrays beginning with arr[i]. There are

    (n-i) such subsets. For example [2] appears

    in [2] and [2, 3].

  • In (n-i)*i subarrays where this element is not

    first element. For example [2] appears in

    [1, 2] and [1, 2, 3].

Sum = (n-i) + (n-i)*i = (n-i)(i+1)

public static long SubArraySum( int arr[] , int n )
{
    long result = 0;

    // computing sum of subarray using formula
    for (int i=0; i<n; i++)
        result += (arr[i] * (i+1) * (n-i));
    return result ;
}

Duplicted number increase by 1

E.g. [1,2,2,3,3] -> [1,2,3,4,5]

private static List<Integer> f(int[] A){
    List<Integer> list = new ArrayList<>();
    list.add(A[0]);
    int prev = A[0];
    for(int i=1; i<A.length; i++){
        if(A[i]<=prev) list.add(prev+1);
        else list.add(A[i]);
        prev = list.get(list.size()-1);
    }
    return list;
}
 public static void main(String []args){
     int[] A = new int[]{1,2,2,3,3};
    System.out.println(f(A));
 }