Horje
Identify the Most Strongest Programmer

There are N Players in a Game and you have given M pieces of information about their superiority. The ith information ( infromation[i] = {Ai, Bi} ) states that “Player Ai > Player Bi“, the task is to determine the number of the strongest programmers among the N players based on the provided information. If there is a unique strongest programmer, print their number. Otherwise, if there are multiple possible strongest programmers or cannot be determined, print -1.

Examples:

Input: N = 3, M = 2, information[] = [[1, 2], [2, 3]]
Output: 1

Input: N = 6, M = 6, information[] = [[1, 6], [6, 5], [6, 2], [2, 3], [4, 3], [4, 2]]
Output: -1

Approach: To solve the problem follow the below idea:

This problem can be solved using transitive property and some observations.

  • If there exists a player for which there are no other players stronger than him then he will be the strongest player.
  • To efficiently determine the strongest player among N competitors, We count how many people are stronger than each player.
  • It iterates through the given information, updating the count based on the transitive nature of superiority.
  • It then checks if there is exactly one candidate with zero stronger players, indicating the strongest person.
  • If there are multiple candidates, it cannot identify the Most strongest player in that case we return -1.

Steps to solve the problem:

  • Read the input values N (the number of programmers) and M (the number of pieces of information).
  • Create a vector deg[] to keep track of the count of people stronger than each person i. Initialize all elements of deg[] to 0.
  • For each pair of information (A[i], B[i]) in the given M pieces of information, This step is equivalent to adding 1 to the count of people stronger than each programmer A[i].
  • Initialize the answer variable ans to -1, which will store the result.
  • Iterate over all the player from 1 to N.
  • If there is a player i having deg[i] = 0, then assign i to strongest player and if strongest programmer is not -1 , i.e. there exist another stronger programmer then print -1 and exit the code.
  • In the end print strongest programmer

Below is the implementation of above approach:

C++

// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the strongest programmer
int findStrongestProgrammer(int N, int M,
                        vector<pair<int, int> > power)
{
    vector<int> deg(N + 1, 0);
 
    // Taking indegree
    for (int i = 0; i < M; i++) {
        int a = power[i].first;
        int b = power[i].second;
        deg[b]++;
    }
    int strongest_programmer = -1;
 
    // Finding the strongest programmer
    for (int i = 1; i <= N; i++) {
        if (deg[i] == 0) {
            if (strongest_programmer != -1) {
                return -1;
            }
            else {
                strongest_programmer = i;
            }
        }
    }
    return strongest_programmer;
}
 
// Drivers code
int main()
{
    int N = 3, M = 2;
    vector<pair<int, int> > power = { { 1, 2 }, { 2, 3 } };
 
    // Function Call
    int result = findStrongestProgrammer(N, M, power);
 
    if (result == -1) {
        cout << -1 << endl;
    }
    else {
        cout << result << endl;
    }
    return 0;
}

Java

public class GFG {
     
    static int findStrongestProgrammer(int N, int M, int[][] power) {
        int[] deg = new int[N + 1];
 
        // Taking indegree
        for (int i = 0; i < M; i++) {
            int b = power[i][1];
            deg[b]++;
        }
 
        int strongestProgrammer = -1;
 
        // Finding the strongest programmer
        for (int i = 1; i <= N; i++) {
            if (deg[i] == 0) {
                if (strongestProgrammer != -1) {
                    return -1;
                } else {
                    strongestProgrammer = i;
                }
            }
        }
 
        return strongestProgrammer;
    }
 
    public static void main(String[] args) {
        int N = 3;
        int M = 2;
        int[][] power = new int[M][];
        power[0] = new int[]{1, 2};
        power[1] = new int[]{2, 3};
 
        // Function Call
        int result = findStrongestProgrammer(N, M, power);
 
        if (result == -1) {
            System.out.println(-1);
        } else {
            System.out.println(result);
        }
    }
}
//this code is contributed by rohit singh

Python3

# Function to find the strongest programmer
def findStrongestProgrammer(N, M, power):
    deg = [0] * (N + 1)
 
    # Taking indegree
    for i in range(M):
        a, b = power[i]
        deg[b] += 1
 
    strongest_programmer = -1
 
    # Finding the strongest programmer
    for i in range(1, N + 1):
        if deg[i] == 0:
            if strongest_programmer != -1:
                return -1
            else:
                strongest_programmer = i
 
    return strongest_programmer
 
# Driver code
if __name__ == "__main__":
    N = 3
    M = 2
    power = [(1, 2), (2, 3)]
 
    # Function Call
    result = findStrongestProgrammer(N, M, power)
 
    if result == -1:
        print(-1)
    else:
        print(result)
 
#Contributed by Aditi Tyagi

C#

//C# code for the above approach:
 
using System;
 
class Program
{
    static int FindStrongestProgrammer(int N, int M, int[][] power)
    {
        int[] deg = new int[N + 1];
 
        // Taking indegree
        for (int i = 0; i < M; i++)
        {
            int b = power[i][1];
            deg[b]++;
        }
 
        int strongestProgrammer = -1;
 
        // Finding the strongest programmer
        for (int i = 1; i <= N; i++)
        {
            if (deg[i] == 0)
            {
                if (strongestProgrammer != -1)
                {
                    return -1;
                }
                else
                {
                    strongestProgrammer = i;
                }
            }
        }
 
        return strongestProgrammer;
    }
 
    static void Main()
    {
        int N = 3;
        int M = 2;
        int[][] power = new int[M][];
        power[0] = new int[] { 1, 2 };
        power[1] = new int[] { 2, 3 };
 
        // Function Call
        int result = FindStrongestProgrammer(N, M, power);
 
        if (result == -1)
        {
            Console.WriteLine(-1);
        }
        else
        {
            Console.WriteLine(result);
        }
    }
}
 
// this code is contributed by uttamdp_10

Javascript

// JavaScript code for the above approach:
 
// Function to find the strongest programmer
function findStrongestProgrammer(N, M, power) {
    const deg = new Array(N + 1).fill(0);
 
    // Taking indegree
    for (let i = 0; i < M; i++) {
        const a = power[i][0];
        const b = power[i][1];
        deg[b]++;
    }
 
    let strongestProgrammer = -1;
 
    // Finding the strongest programmer
    for (let i = 1; i <= N; i++) {
        if (deg[i] === 0) {
            if (strongestProgrammer !== -1) {
                return -1;
            } else {
                strongestProgrammer = i;
            }
        }
    }
     
    return strongestProgrammer;
}
// Drivers code
 
const N = 3;
const M = 2;
const power = [[1, 2], [2, 3]];
 
// Function Call
const result = findStrongestProgrammer(N, M, power);
 
if (result === -1) {
    console.log(-1);
} else {
    console.log(result);
}

Output

1

Time Complexity: O(N+M)
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Minimum time to reduce all the elements to zero Minimum time to reduce all the elements to zero
Online Postfix to Prefix Converter Online Postfix to Prefix Converter
Prefix to Postfix Converter Online Prefix to Postfix Converter Online
Array Sum Array Sum
Number of Islands in a Circular Matrix Number of Islands in a Circular Matrix

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 15



 

Horje