Last Updated: 27 Oct, 2021
Bob’s Robot
Easy
Asked in company
There were ‘N’ robots placed one after another, ith of which has a power ‘P[i]’. Bob picks the robot having the highest power. Now Bob’s robot will fight with all the other ‘N’ - 1 robot. In every fight, Bob’s robot wins if the power of his robot is greater than or equal to twice the power of the other robot.
If Bob can win all the fights, return the index of the robot Bob selects, else print -1.
Note: The frequency of the largest number will always be 1 in the array ‘P’.
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains one integer ‘N’, denoting the number of robots.
The following line contains an array ‘P’ of ‘N’ spaced integers denoting the power of each robot.
Output Format:
For each test case, print a single integer denoting the index of the robot Bob has selected or -1 if Bob’s robot can not win all the fights.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 5
1 <= N <= 10^5
1 <= A[i] <= 10^9
Time Limit: 1 sec
Approaches
Firstly we need to find the power of the robot Bob will select, which will be equal to the maximum value present in the array ‘P’. After finding the maximum value of the array, we need to compare it with all the other values in the array. If the maximum value is greater than or equal to twice the values of other robots, we will return the index of the maximum value else, return -1.
Algorithm:
- Initialise ‘mx’ to 0
- Iterate through the array ‘P’
- Update ‘mx’ to the maximum of ‘mx’ and the current element.
- Initialise ‘ans’ to -1
- .Run a loop ‘i’ from 0 to ‘N’ - 1
- If ‘P[i]’ is equal to ‘mx’ then update ‘ans’ to ‘i’ and continue.
- If 2 * ‘P[i]’ is greater than ‘mx’ return -1
- Return ‘ans’
Similar problems