Bob’s Robot

Easy
0/40
Average time to solve is 20m
profile
Contributed by
2 upvotes
Asked in company
Google inc

Problem statement

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

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4 
2 1 3 7
2
8 9
Sample Output 1:
3
-1
Explanation for Sample Input 1:
In the first test case, Bob can select the robot at index 3 having power 7. Since 7 is greater than or equal to twice the power of other robots, Bob wins all the fights.  
In the second test case, the robot with the highest power .i.e 9, is not greater than or equal to twice the power of the other robots as 2 * 8 > 9.
Sample Input 2:
2
5 
9 1 3 1 1
3 
2 3 2
Sample Output 2:
0 
-1
Hint

Can you find the robot with maximum power and check if this robot can win against all the other robots?

Approaches (1)
Implementation

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

O(N), where ‘N’ is the size of the array ‘P’

Since we are iterating through the array two times, the time complexity is O(N).


 

Space Complexity

O(1)

We are using constant extra space.


 

Code Solution
(100% EXP penalty)
Bob’s Robot
Full screen
Console