[Solution] Subtract 12 Operation solution codechef

Table of Contents

Subtract 12 Operation solution codechef

Subtract 12 Operation solution codechef – You are given N integers A_1, A_2, \ldots, A_N.

You can perform the following operation any number of times:

  • Select any index i such that 1 \le i \le (N-1);
  • Subtract 1 from A_i and 2 from A_{i+1}.

Find the smallest possible value of |A_1| + |A_2| + \ldots + |A_N| you can achieve after performing any number of given operations.

Subtract 12 Operation solution codechef

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains a single integer N — the number of integers.
    • The second line of each test case contains N integers A_1, A_2, \ldots, A_N.

Output Format

For each test case, output a single integer — the smallest possible value of |A_1| + |A_2| + \ldots + |A_N| you can achieve after performing any number of given operations.

Constraints

  • 1 \leq T \leq 100000
  • 1 \leq N \leq 2 \cdot 10^5
  • -10^9 \le A_i \le 10^9
  • The sum of N over all test cases won’t exceed 2 \cdot 10^5.

Subtract 12 Operation solution codechef

Input

Output

4
2
2 4
3
1 1 1
6
-4 2 -4 2 -4 2
1
-100000000
0
2
15
100000000

Subtract 12 Operation solution codechef

Test case 1: We can apply the operation for i = 1. Thus, the array becomes A = [1, 2]. On applying the operation again for i=1, the array becomes A = [0, 0]. Thus, the value of |A_1| + |A_2| = 0. It can be shown that this is the smallest possible value of |A_1| + |A_2|.

Test case 2: Apply the operation for i = 1. The array becomes A = [0, -1, 1]. Apply the operation again for i=2. The array becomes A = [0, -2, -1]. Thus, the value |A_1+|A_2|+|A_3| = 0+2+1 = 3.

Test case 3: We apply three operations on indices 1, 3, and 5 respectively. Thus, the final array becomes A = [-5, 0, -5, 0, -5, 0]. The value |A_1| + |A_2| + \ldots + |A_6| = 15.

Test case 4: We cannot apply any operation on the array as we cannot choose any valid index.

For Solution

“Click Here”

Leave a Comment