Absolute difference in an array

Easy

0/40

Average time to solve is 15m

Contributed by

12 upvotes

Asked in companies

Problem statement

You are given an array/list 'ARR' consisting of 'N' non - negative integers. Your task is to return the running absolute difference of the elements at even and odd index positions separately.

The index of the first element in the array is considered to be zero that is 0 - based indexing is considered for calculating the parity of the index.

Example:

Consider the array - [1, 2, 3, 4, 5, 6]
The elements at even positions will be 1, 3, 5. The running absolute difference of elements will be - 
|1 - 3| = 2 , |2 -5| = 3. Hence our answer will be 3.

The elements at odd positions will be 2, 4, 6. The running absolute difference of elements will be - 
|2 - 4| = 2 , |2 - 6| = 4. Hence our answer will be 4.

Detailed explanation ( Input/output format, Notes, Images )

Input Format

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test cases follow.

The first line of each test case contains a single integer ‘N’ denoting the number of elements of ARR.

The next line of each test case contains ‘N’ space-separated integers denoting the elements of ARR.

Output Format :

For each test case, return two integers denoting the running absolute difference of elements at even and odd positions respectively.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

 1 <= T <= 10
 1 <= N <= 5 * 10^4
 1 <= ARR[i] <=10^5

Time Limit: 1 sec

Sample Input 1:

Sample Output 1:

0 0
0 4

Explanation of Input 1:

For test case 1:
• The running absolute difference of elements at even positions will be : |5 - 3| = 2, |2 - 2| = 0.
• The running absolute difference of elements at odd positions will be : |4 - 4| = 0.
For test case 2:
• The running absolute difference of elements at even positions will be : |3 - 3| = 0.
• The running absolute difference of elements at odd positions will be : |5 - 1| = 4.

Sample Input 2:

1
7
10 20 30 40 50 60 70

Sample Output 2:

40 40

Hint 1

Try to simulate the above operations.

Approaches (1)

Approach 1

Simulation

We will keep two variables 'SUM_EVEN’ and ‘SUM_ODD' initially initialised to zero, denoting the running absolute difference of elements at even and odd positions respectively. For each index ‘i’, if ‘i’ is even, we set 'SUM_EVEN' to |'SUM_EVEN' - ‘ARR[i]’| else, we set 'SUM_ODD' to |'SUM_ODD' - ‘ARR[i]’|.

The algorithm will be -

For each ‘i’ from 0 to ‘N - 1’:
- If ‘i’ % 2 == 0 :
  - 'SUM_EVEN' = |'SUM_EVEN' - ARR[i]|.
- Else,
  - 'SUM_ODD' = |'SUM_ODD' - ARR[i]|.
We finally return the value of 'SUM_EVEN' and 'SUM_ODD'.

Time Complexity

O(N), where ‘N’ is the total number of elements of ‘ARR’.

As every element of ‘ARR’ will be visited at most once, the time complexity will be O(N).

Space Complexity

O(1).

Constant space is used.

(100% EXP penalty)

Absolute difference in an array

Console