Last Updated: 17 Feb, 2021

Raid In The City

Easy

Asked in company

Solve now

Problem statement

In a city, there are N houses in a line. Each house is 1 unit apart from the other i.e. distance between any two adjacent houses is 1 unit. The city has both corrupt and honest inhabitants. As a result, some houses contain black money while some contain white money.

The government of India decided to raid this city. Now people having black money want to convert it into white money as soon as possible. The only possible way to do this conversion is to take the black money to the houses with white money. But there is the following restriction: The maximum amount of black money that a white money house can convert is equal to the amount of money that the white house contains.

Note:

We are representing white money as positive integers and black money as negative integers.

For example:

Let‘s assume ‘HOUSES’ =   [2, -2, -1, 2, -1]. In this example ‘HOUSES[0]’ and ‘HOUSES[3]’ ( 0-based indexing) contain white money while ‘HOUSES[1]’, ‘HOUSES[2]’ and ‘HOUSES[4]’ and  (0-based indexing) contain black money.

The cost of transferring money from one house to another house is the distance between these houses * amount of money transferred.

For example:

Let‘s assume ‘HOUSES’ =   [2, -2, -1, 2, -1]. If we want to transfer all black money from ‘HOUSE[1]’ to ‘HOUSE[3], then the cost of transferring the money is (abs(1 - 3) * (2)) => 4.

Your task is to find the minimum cost of converting all the black money into white.

Note:

The sum of the amount of black money in all houses is exactly equal to the sum of the amount of white money in all houses.

Input Format

The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains a single integer ‘N’ representing the number of houses in the city.

The next line of each test case contains ‘N’ single space-separated integers denoting the amount of money in the houses.

Output Format :

For each test case, print the minimum cost of converting all the black money into white money.

Print the output of each test case in a separate line.

Note:

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

Constraints:

1 <= ‘T’ <= 100
2 <= ‘N’ <= 5000
-10^5 <= ‘HOUSES[i]’ <= 10^5

Time Limit: 1 second

Solve now

Approaches

01 Approach

As we know we can choose any house which contains black money for converting it to white money. But the efficient way is to choose the nearest house which contains white money. For this first, we can put all the black money and their respective house number into a list/vector and do the same for the white money houses. And then we remove the 0’th elements of list/vector ‘blackMoneyList’ and ‘whiteMoneyList’ and start converting the black money to white money till the whole black money is not converted into white money.

Here is the algorithm :

We declare two lists/vectors ‘blackMoneyList’ and ‘whiteMoneyList’ in which we store the black money amount and the respective house number and white money amount and respective house number.
We declare a variable ‘totalCost’ in which we store the minimum cost of conversion till now.
We run a while loop till both lists/vectors are not empty, remove the 0’th elements of both of the lists/vectors:
- If the 0’th element of the ‘blackMoneyList’ and ‘whiteMoneyList’ are equal:
  - ‘totalCost’ = abs(‘blackMoneyListEle.index’ - ‘whiteMoneyListEle’) * ‘blackMoneyListEle.amount’.
- If the amount of ‘blackMoneyListEle’ is more:
  - ‘totalCost’ = abs(‘blackMoneyListEle.index’ - ‘whiteMoneyListEle’) * ( ‘blackMoneyListEle.amount’ - ‘whiteMoneyListEle.amount’)
  - ‘blackMoneyListEle.amount’ - = ‘whiteMoneyListEle.amount.
  - Add this remaining ‘blackMoneyListEle.amount’ into the ‘blackMoneyList’.
- Else
  - ‘totalCost’ = abs(‘blackMoneyListEle.index’ - ‘whiteMoneyListEle’) * ( ‘whiteMoneyListEle.amount’ - ‘blackMoneyListEle.amount’)
  - ‘whiteMoneyListEle.amount’ - = ‘blackMoneyListEle.amount.
  - Add this ‘whiteMoneyListEle.amount’ into the ‘whiteMoneyList’.
4. Finally, return ‘totalCost’.

Solve now

02 Approach

As we know, the amount of black money and white money is the same. So we can greedily pick the nearest white money house for converting the black money to white money. So we traverse at every index and we pick money whether it is white or black and add it to the variable ‘currMoney’ in which we store the amount of money from house number 0 to current house. That is, we traverse at every index of the ‘HOUSES’ and store a cumulative amount of money till now. At every index, we add abs(‘currMoney’) * 1 into ‘totalCost’ in which we store the minimum amount of cost of converting all the black money into white. And we multiply ‘currMoney’ by 1 because the distance between any two adjacent houses is 1.

Here is the algorithm :

We declare variables ‘currMoney’ and ’totalCost’ in which we store the amount of money from house number 0 to the current house and minimum cost of conversion till now, respectively.
We run a loop for ‘i’ = ‘0’ to ‘N’:
- ‘currMoney’ += ‘HOUSE[i]’.
- ‘totalCost’ += abs(‘currMoney’)
Finally, we return the ‘totalCost’.

Solve now