1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force Approach
3.
Optimized Approach(Maths + Sorting):
3.1.
Implementation in C++
3.1.1.
Complexity Analysis
4.
5.
Key takeaways
Last Updated: Mar 27, 2024

# Minimum Loss

## Introduction

### Problem Statement

The problem states we are N students numbered from 1 to N in the queue. Each student is having two numbers, let say Pi and Qi. The loss of the student is defined as the sum of the product of Pi with the number of students to the left and Qi with the number of students to the right. Let say student i, is at position j, then its loss is given by Pi*(j-1) + Qi(N-j). We are allowed to rearrange the students in the queue and need to minimize the total loss, where total loss is the sum of the loss of every student.

``````Input Format :
The First Line contains an integer N, denoting the total number of students.
Next, the N line contains two integers Pi and Qi.
Output Format:
The output will contain only a single integer denoting the minimum possible
loss by rearranging the student in the queue. ``````

We will discuss the brute and optimized approach, along with a dry run on sample example and c++ code.

### Sample Examples

``````Input:
4
2 4
3 3
7 1
2 3
Output: 25
Explanation:
In this example, it is optimal to put the students in the order {4, 2, 1, 3}, this will give us the minimum total possible loss.
The first student is in fourth position, so his loss is : 2*(3) + 3*(0) = 6.
The second student is in second position, so his loss is : 3*(1) + 3*(2) = 9.
The third student is in the first position, so his loss is 7*(0) + 1*(3) = 3
The fourth student is in third position, so his loss is 2*(2) + 3*(1) = 7
So Total loss is 6 + 9 + 3 + 7 = 25, which is minimum loss possible.  ``````

## Brute Force Approach

In the brute force approach, we can generate all possible permutations of the N students which are N! possibilities, and calculate the loss for every permutation in O(N). Then we will take the minimum possible total loss out of all the possible answers. We can see this approach is highly inefficient as it takes N*N! operations for finding the solution.

## Optimized Approach(Maths + Sorting):

We can see that we need to calculate the minimum loss of Pi*(j-1) + Qi(N-j) for all student i standing at position j.  Let’s Simplify this equation :

R = Pi*(j-1) + Qi(N-j)

R = Pi*j - Pi + Qi*N - Qi*j

Taking j common from Pi*j - Qi*j

R = j(Pi-Qi) + (Qi*N - Pi)

Let x = Qi*N - Pi

Let y = j(Pi-Qi)

We can clearly see that Qi*N - Pi is constant for any student, i. We can directly add this part into our total loss.

So our main aim is to minimize the value of (Qi-Pi)*j. Since (Qi-Pi) is also fixed for any student i, so to minimize the x we need to multiply the highest value of (Qi-Pi) for any i, with the smallest j, and similarly second highest value of (QiPi) with the second smallest j. We can achieve this by calculating (Qi-Pi) for every i, then sorting them in ascending order.

Finally, We will calculate the result of (Pi-Qi)*j + (Qi*N - Pi), and sum them for all values i. It is guaranteed that this will be the smallest possible value of the total loss.

Let’s Dry run for the above sample test case.

4

2 4

3 3

7 1

2 3

Let’s denote X = Qi*N - Pi and Y = Pi-Qi, we will calculate x and y for each and every student, starting with student 1. Let say totalLoss = 0 holds the final Output, We will add the value of X into the total sum as X is constant in nature.

For Student 1:

Pi = 2, Qi = 4

X = Qi*N - Pi = (4*4 - 2) = 14

Y =  Pi-Qi = 2 - 4 = -2

totalLoss  = 0 + 14

For Student 2:

Pi = 3, Qi = 3

X = Qi*N - Pi = (3*4 - 3) = 9

Y =  Pi-Qi = 3 - 3 = 0

totalLoss = 14 + 9 = 23

For student 3:

Pi = 7, Qi = 1

X = Qi*N - Pi = (1*4 - 7) = -3

Y =  Pi-Qi = 7 - 1 = 6

totalLoss = 23 - 3 = 20

For Student 4:

Pi = 2, Qi = 3

X = Qi*N - Pi = (3*4 - 2) = 10

Y =  Pi - Qi = 2 - 3 = -1

TotalLoss = 20 + 10 = 30

Now we got the Y array as [-2,0,6,-1] and TotalLoss = 30. We will sort the array Y in descending order so that the highest value will be multiplied by the lowest j, after sorting the array will look like [6,0,-1,-2].

Now we will add Y*j into the total Sum. starting with j = 1

TotalLoss = 30 + (6*1) + (0*2) + (-1*3) + (-2*4) = 25.

So minimum loss is 25.

Now the logic should be clear, now let’s implement the above logic into the C++ code.

### Implementation in C++

``````// c++ code for finding the minimum loss
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
// this will store the value of p-q as explained above
int Y[n];
// it will store the sum of minimum loss
int totalLoss = 0;
for(int i=0;i<n;i++){
int p,q;
cin >> p >> q;
Y[i] = p-q;
// adding q*n - p into the total sum
// because this is the constant part
totalLoss += q*n - p;
}
// sorting the array that stores p-q in descending order
sort(Y,Y+n,greater<int>());
// adding (p-q)*j into the totalSum
for(int j=0;j<n;j++){
totalLoss += Y[j]*(j+1);
}
// printing the totalSum, which is minimum loss
cout << totalLoss << endl;
}``````

Output:

``25``

#### Complexity Analysis

Time Complexity: O(NlogN)

Explanation: (NlogN) is used for sorting the Y array into descending order.

Space ComplexityO(N)

Explanation: It is used by Y array, for storing the value of {P-Q}.

Q1. Which sorting algorithm is used when we sort using STL?

Ans. The sorting algorithm used in STL sort() is IntroSort. Introsort is a hybrid sorting algorithm that uses three sorting algorithms to minimize the running time. These algorithms are quicksort, Heapsort, and Insertion Sort.

Q2. What is the greedy approach?

Ans. It is an algorithm to get the optimal solution for the problem. In this algorithm, we always choose the next best solution that seems optimal at that step. We build solutions piece by piece to reach the optimal solution.

Q3. How many permutations if there are some identical elements?

Ans. Repetitions in the array are taken care of by dividing the permutation by the factorial of identical objects.

## Key takeaways

In this article, we discussed the problem of finding the minimum sum under the given constraints. We discussed the two approaches, i.e., brute force and optimized approach using maths and sorting. We hope you understand the problem and solution properly. Now you can do more similar questions.

If you are a beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free!