#### CONCEPTS USED:

Basic Mathematics

#### DIFFICULTY LEVEL:

Hard

#### PROBLEM STATEMENT`(`

SIMPLIFIED`)`

:

Given a magical container such that whenever :-

- A Red Stone is added to the
`i^{th}`

bag, the quality factor of`i`

to`N`

bags increases by`1`

.- A Black Stone is added to the
`i^{th}`

bag, the quality factor of`i`

to`N`

bags decreases by`1`

.Given an array of

`N`

bags, task is to perform minimum no. of operations on the magical container and equalise both the containers.

**See original problem statement here**

#### For Example:

```
Input : N = 5, A[] = [1, 2, 3, 4, 5]
Output : 5
Explanation :
Quality factor of given container [1, 2, 3, 4, 5]
Quality factor of magical container [0, 0, 0, 0, 0]
Adding a Red stone at index 0,
Quality factor of given container [1, 2, 3, 4, 5]
Quality factor of magical container [1, 1, 1, 1, 1]
Adding a Red stone at index 1,
Quality factor of given container [1, 2, 3, 4, 5]
Quality factor of magical container [1, 2, 2, 2, 2]
Adding a Red stone at index 2,
Quality factor of given container [1, 2, 3, 4, 5]
Quality factor of magical container [1, 2, 3, 3, 3]
Adding a Red stone at index 3,
Quality factor of given container [1, 2, 3, 4, 5]
Quality factor of magical container [1, 2, 3, 4, 4]
Adding a Red stone at index 4,
Quality factor of given container [1, 2, 3, 4, 5]
Quality factor of magical container [1, 2, 3, 4, 5]
Both containers are equalised by performing 5 operations.
```

#### OBSERVATION:

Whenever a stone is added to a bag, it affects all the bags from

`i`

to`N`

bags i.e. all bags including the current one and all to the right of it. While the left bags remain unchanged.

Can you now think of something that can be used using this Hint before going to the solution?

#### SOLVING APPROACH:

The approach is to start from the left most side of the array and keep on equalising the elements in both the arrays. Because once we move ahead, our next actions will not disturb the left side of the array.

Initialise

`current`

and`total`

as`0`

and start traversing the array from the left.for every element

`A[i]`

, the absolute difference between the element and`current`

is the number of operations required to equalise`ith`

element of the`Magical container`

with`A[i]`

, keep adding the absolute difference to`total`

. Also update`current`

with`A[i]`

.Keep following the same procedure for equalising each and every element the best online learning sites for programming.

#### ILLUSTRATION:

```
A[] = [1, 2, 3, 2]
Q[] = [0, 0, 0, 0]
count = 0
current = 0
i = 0
count = count + abs(A[i] - current) = 0 + abs(A[0] - 0) = 0 + 1 = 1
current = A[0] = 1
i++
i = 1
count = count + abs(A[i] - current) = 1 + abs(A[1] - 1) = 1 + abs(2 - 1) = 2
current = A[1] = 2
i++
i = 2
count = count + abs(A[i] - current) = 2 + abs(A[2] - 2) = 2 + abs(3 - 2) = 3
current = A[2] = 3
i++
i = 3
count = count + abs(A[i] - current) = 3 + abs(A[3] - 3) = 3 + abs(2 - 3) = 4
current = A[3] = 2
i++
Total operations to be performed are 4.
```

#### SOLUTIONS:

[TABS_R id=654]

[forminator_quiz id=”693″]