|
There is an English competition having two divisions, Speaking and Writing. There are ‘N‘ participants numbered 1 to N, whose skill sets are mentioned in two arrays ‘S‘(speaking) and ‘W‘(writing). All participants have distinct skill set values in the same division. When any two participants compete in a division, the one with the higher skill set wins. A participant’s competence is decided by the total number of individuals they can defeat across both divisions. The participants who have the highest competence will be considered a winner. Find the number of winners of the competition.
Examples:
Input: n = 2, S = {1, 3}, W = {6, 4}
Output: 2
Explanation: The second participant can defeat the first in the speaking division and the first participant can defeat the second in the writing division. Hence a total of 2 winners
Input: n = 5, S = {5, 4, 1, 3, 2}, W = {6, 1, 2, 3, 4}
Output: 1
Explanation: The first participant can defeat all others in both divisions. There is no other participant who can defeat all the four others. Hence there is only 1 winner.
Approach: To solve the problem follow the below idea:
Since there are N participants in total, the maximum competence that any individual can have is N-1. Hence, all participants with a competence of N-1 will be considered winners.
- Add the arrays ‘S’ and ‘W’ in a vector of pairs. pairs[i].first = S[i], pairs[i].second = W[i]
- Sort pairs{S[i], W[i]} in descending order of S[i].
- Let’s consider an example to understand the further implementation: S={4, 3, 1, 2, 6} and W={2, 5, 6, 4, 3}. S[i] is sorted in decreasing order and then both the arrays are stored in the table below:
- It is clear that participant at index 0 will always have a competence of n-1, since it can defeat all individuals in the speaking division from index 1 to 4. No need to check for writing division since all participants are already included. Increase count by 1, count=1
- Participant at index 1 will have a competence of at-least n-2(defeats index 2 to 4 from the speaking division). For the Writing division, If
W[0]<W[1] then the participant at index 1 can also defeat the participant at index 0. Hence the total competence becomes n-2+1 = n-1. Again, increase count by 1, count = 2
- Participant at index 2 will have a competence of at-least n-3(from the speaking division), For writing division, since W[2] >W[1]>W[0], this participant can defeat participants on indexes 0 and 1 , Hence total competence = n-3+2=n-1, count=3
- Hence, it is clear that for a particular index i, if W[i]>W[i-1]>W[i-2]…….W[0], then the total competence at that index will be n-i-1(speaking competence) + i(writing competence) = n-1, and that participant will be considered a winner, otherwise the total competence is just
n-i-1(speaking competence) so the individual won’t be a winner
- So, iterate through the vector pairs, if pairs[i].second ie W[i] is greater than the values at all the previous indexes , then increase the value of count.
Below is the C++ implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int count_of_winners(int N, vector<int>& S, vector<int>& W)
{
vector<pair<int, int>> pairs;
for (int i = 0; i < N; i++) {
pairs.push_back({ S[i], W[i] });
}
sort(pairs.begin(), pairs.end(),
greater<pair<int, int>>());
int cur_max = -1;
int count = 0;
for (int i = 0; i < N; i++) {
if (pairs[i].second > cur_max)
count++;
cur_max = max(cur_max, pairs[i].second);
}
return count;
}
int main()
{
int N;
N = 5;
vector<int> S = { 4, 3, 1, 2, 6 };
vector<int> W = { 2, 5, 6, 4, 3 };
cout << count_of_winners(N, S, W) << "\n";
return 0;
}
|
Java
import java.util.*;
class Main {
static int countOfWinners(int N, List<Integer> S, List<Integer> W) {
List<AbstractMap.SimpleEntry<Integer, Integer>> pairs = new ArrayList<>();
for (int i = 0; i < N; i++) {
pairs.add(new AbstractMap.SimpleEntry<>(S.get(i), W.get(i)));
}
pairs.sort((a, b) -> b.getKey().compareTo(a.getKey()));
int curMax = -1;
int count = 0;
for (int i = 0; i < N; i++) {
if (pairs.get(i).getValue() > curMax) {
count++;
}
curMax = Math.max(curMax, pairs.get(i).getValue());
}
return count;
}
public static void main(String[] args) {
int N = 5;
List<Integer> S = Arrays.asList(4, 3, 1, 2, 6);
List<Integer> W = Arrays.asList(2, 5, 6, 4, 3);
System.out.println(countOfWinners(N, S, W));
}
}
|
Python3
def count_of_winners(N, S, W):
pairs = [(S[i], W[i]) for i in range(N)]
pairs.sort(reverse=True)
cur_max = -1
count = 0
for i in range(N):
if pairs[i][1] > cur_max:
count += 1
cur_max = max(cur_max, pairs[i][1])
return count
if __name__ == "__main__":
N = 5
S = [4, 3, 1, 2, 6]
W = [2, 5, 6, 4, 3]
print(count_of_winners(N, S, W))
|
C#
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static int CountOfWinners(int N, List<int> S, List<int> W)
{
List<Tuple<int, int>> pairs = new List<Tuple<int, int>>();
for (int i = 0; i < N; i++)
{
pairs.Add(new Tuple<int, int>(S[i], W[i]));
}
pairs = pairs.OrderByDescending(t => t.Item1).ToList();
int curMax = -1;
int count = 0;
for (int i = 0; i < N; i++)
{
if (pairs[i].Item2 > curMax)
count++;
curMax = Math.Max(curMax, pairs[i].Item2);
}
return count;
}
static void Main(string[] args)
{
int N = 5;
List<int> S = new List<int> { 4, 3, 1, 2, 6 };
List<int> W = new List<int> { 2, 5, 6, 4, 3 };
Console.WriteLine(CountOfWinners(N, S, W));
}
}
|
Javascript
function countOfWinners(N, S, W) {
const pairs = [];
for (let i = 0; i < N; i++) {
pairs.push([S[i], W[i]]);
}
pairs.sort((a, b) => b[0] - a[0]);
let curMax = -1;
let count = 0;
for (let i = 0; i < N; i++) {
if (pairs[i][1] > curMax)
count++;
curMax = Math.max(curMax, pairs[i][1]);
}
return count;
}
const N = 5;
const S = [4, 3, 1, 2, 6];
const W = [2, 5, 6, 4, 3];
console.log(countOfWinners(N, S, W));
|
Time Complexity: O(N*logN), where N is the number of participants
Auxiliary Space: O(N), where N is the number of participants, because a vector of pairs of size N is used
|
.png){kind=small}