Count Of Plates

Easy
0/40
Average time to solve is 15m
33 upvotes
Asked in company
HSBC

Problem statement

You are given 3 Integers ‘n’, ‘R’ & ‘r’ where ‘n’ is the number of plates,

‘R’ is the radius of the table, and ‘r’ is the radius of the ‘n’ plates. The task is to find out whether the given table has enough space to accommodate the given number of plates of radius ‘r’. Consider the table and plates to be round and no plate can be placed above any other.

Each plate must be completely inside the table and must touch the edge of the table. Of course, the plates must not intersect, but they can touch each other.

You have to return true if the table can accommodate the given number of plates else return false.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains 3 space-separated integers ‘n’, ‘R’ & ‘r’
Output format : 
For each test case, print Yes if the table can accommodate the given number of plates else print No.

Print the output of each test case in a new line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10^5
1 <= n <= 10^6
1 <= r <= 10^9
1 <= R <= 10^9
1 <= r <= R

Time Limit: 1 sec
Sample Input 1
3
4 10 4
5 10 4
1 10 10
Sample Output 1
Yes
No
Yes
Explanation Of Sample Input 1 :
Test Case 1: n = 4 , R = 10 , r = 4
One of the possible arrangements can be : 


Test case 2 : n = 5, R = 10, r = 4
From the above figure we can see that we can place no more plates with “r” = 4.
So, we print No.

Test case 3 : n = 1, R = 10, r = 10
Since R=r , and n=1 so we can place the only plate over the table such that it overlaps
with the table.


So, we print Yes.
Sample Input 2
2
2 10 5
10 10 10
Sample Output 2
Yes
No
Hint

Think about the constraint , each plate of radius r must touch the edge of the table.

Approaches (1)
Optimal Approach

 

Approach : 

 

Since each plate must touch the table, the center of these plates will lie in a circle of Radius  ( R - r ). 

 

Let us say, all the n plates can be accommodated on the table. In this case, all the plates will touch each other and their center will form a regular polygon.

Now, consider the right angled triangle ABO formed in the figure below : 


 

Clearly, AB = r, AO = R - r and Angle(ABO) = 90 degrees

Also, since we need to place n plates, the center angle will be divided into n equal parts, so 

Angle ( AOB ) = PI / n.


 

Now, we apply trigonometry in the above triangle :

  • sin ( AOB ) = r / ( R - r )

 

  • sin ( PI / n ) =  r / ( R - r )

 

But, since this is the case for most plates to fit, we can derive the general rule as : 


 

  • sin ( PI / n ) > = r / ( R - r ) or,
  • PI  >= n * sin-1 ( r / ( R - r ) )

 

If the above equality holds, then we can return true as all plates can be placed on the table, else we return false.
 

Special Cases : 
 

  • If n=1. Return true only if r<=R holds true.
     
  • If R=r, and n != 1 , then return false.
     

Algorithm : 

  • Make a constant PI = 3.1415927
  • If n=1, we just check if r<=R holds true.
    • If it holds true, we return true. else, we return false.
  • Store the value of r / ( R- r ) in a double variable “angle”.
  • Initialize “sineValue” as Math.asin ( angle ).
  • Multiply the “sineValue” by n
  • Check if “sinValue” <= PI
  • If the above equation holds true, return true. else return false.
Time Complexity

O(1)

Since we are doing constant time operations, the overall time complexity is O(1).

Space Complexity

O(1)
 

Constant extra space is required. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Count Of Plates
Full screen
Console