Raid In The City

Easy
0/40
Average time to solve is 15m
profile
Contributed by
5 upvotes
Asked in company
Intuit

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5
5 -4 1 -3 1
4
1 2 -1 -2
Sample Output 1:
9
6

Explanation For Sample Output 1:

For sample test case 1: 

In this sample test case
First, we pick ‘HOUSES[1]’ (0-based indexing) and transfer all the black money to ‘HOUSES[0]’. The cost of converting this black money into white money is abs(1 - 0) * 4 (i.e TotalCost = 4). Now ‘HOUSES’ = [1, 0, 1, -3 , 1]

Then, we pick  ‘HOUSES[3]’ and transfer black money to ‘HOUSES[0]’.  ‘HOUSES[0]’ contains only 1 unit of white money so we can convert only 1 unit of black money to white money. The cost of converting 1 unit of black money into white money is abs(3 - 0) * 1. (i.e TotalCost = 7). Now ‘HOUSES’ = [0, 0, 1, -2, 1].

Then, we pick ‘HOUSES[2]’ and the cost of converting 1unit of black money into white money is abs(3 - 2) * 1 (i.e TotalCost = 8). Now ‘HOUSES’ = [0, 0, 0, -1, 1].

Finally, we pick  ‘HOUSES[4]’ and the cost of converting 1 unit of black money into white money is abs(3 - 4) * 1 (i.e TotalCost = 9). Now ‘HOUSES’ = [0, 0, 0, 0, 0] and there exists no more black money


For sample test case 2: 

In this sample test case
First, we pick ‘HOUSES[2]’ (0-based indexing) and transfer all the black money to  ‘HOUSES[0]’. The cost of converting this black money into white money is abs(2 - 0) * 1 (i.e TotalCost = 2). Now ‘HOUSES’ = [0, 2, 0, -2].

Finally, we pick  ‘HOUSES[3]’and transfer all the black money to  ‘HOUSE[1]’. The cost of converting this black money into white money is abs(3 - 1) * 2 (i.e TotalCost = 6) .Now ‘HOUSES’ = [0, 0, 0, 0] and there exists no more black money.
Sample Input 2:
2
4
12 -4 -4 -4
4
-4 -4 4 4
Sample Output 2:
24
16
Hint

Can you think of choosing the nearest house each time?

Approaches (2)
Brute Force

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’.
Time Complexity

O(N) where ‘N’ represents the number of houses in the city.

 

Initially, we are storing all the black Money amount and house numbers (and white Money amount and house number) in 2 lists/vectors. Then we are traversing the lists/vectors till both the lists/vectors are empty and in every iteration, we are removing at least one element from them. So in the worst case, we have to run this loop N time which is equal to the number of houses.

Space Complexity

O(N)  where ‘N’ represents the number of houses in the city.

 

Initially, we are storing all the black Money amount and house numbers (and white Money amount and house number) in 2 lists/vectors. In the worst case, the size of either of the 2 lists/vectors can be ‘N’ - 1.

For example: For ‘HOUSES’ = [1, 2, 3, -6], the size of the ‘whiteMoneylist’ is 3.

Code Solution
(100% EXP penalty)
Raid In The City
Full screen
Console