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));
}
Last updated
Was this helpful?