# Maximum Area Serving Cake Google OA 2023

## Maximum Area Serving Cake Google OA 2023 Solution

Given an array containing the radii of circular cakes and the number of guests, determine the largest piece that can be cut from the cakes such that every guest gets a piece of the cake with the same area. It is not possible that a single piece has some part of one cake and some part of another cake and each guest is served only one piece of cake.

Example 1:

Input: radii = [1, 1, 1, 2, 2, 3], numberOfGuests = 6.
Output: 7.0686

Explanation:

• Reason being you can take the area of the cake with a radius of 3, and divide by 4. (Area 28.743 / 4 = 7.0686)
• Use a similary sized piece from the remaining cakes of radius 2 because total area of cakes with radius 2 are > 7.0686

Example 2:

Input: radii = [4, 3, 3], numberOfGuests = 3
Output: 28.2743

Example 3:

Input: radii = [6, 7], numberOfGuests = 12
Output: 21.9911

### SOLUTION

Program: Maximum Area Serving Cake solution in Python

``````def maximumAreaServingCake(radii, numberOfGuests):
areas = [math.pi * r * r for r in radii]
def possible(x):
k = 0
for a in areas:
k += a // x
if k >= numberOfGuests:
return True
return False

l, r = 0, max(areas)
while l + 1e-5 <= r:
x = (l + r) / 2
if possible(x):
l = x
else:
r = x
return round(x, 4)

# Example 1.
radii = [ 1, 1, 1, 2, 2, 3]
numberOfGuests = 6
# Output: 7.0686

# Example 2.
numberOfGuests = 3
# Output: 28.2743

# Example 3.
numberOfGuests = 12
# Output: 21.9911``````

Program: Maximum Area Serving Cake solution in C++

``````#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
double maximum_serving_area(vector<int> v,int k){
double l=0,m=0,x;
vector<double> A;
for(int i=0;i<v.size();i++)  {
x=(double)v[i]*3.141592*v[i];
m=max(m,x);
A.push_back(x);
}
while(m-l>=1e-5){
x=(l+m)/2;
if(check(x,A,k))
l=x;
else m=x;
}
return x;
}
bool check(double &x ,vector<double>&A,int &K){
int k=0;
for(auto a : A){
k+=a/x;
if(k>=K) return true;
}
return false;
}
};
int main(){
int t,n,h,k;
string s1;
Solution s=Solution();
cin>>t;
while(t--){
cin>>n;
vector<int> v(n);
for(int i=0;i<n;i++) cin>>v[i];
cin>>h;
double res=s.maximum_serving_area(v,h);
cout<<fixed<<setprecision(4)<<res;
cout<<endl;
}

}``````

Program: Maximum Area Serving Cake solution in Python

``````import math
def getMaxCake(cakes, P):
def getArea(cake):
return math.pi * cake * cake
N = len(cakes)
dp = []
for i in xrange(0, P + 1):
dp.append(* (N + 1))

for i in xrange(1, N + 1):
dp[i] = getArea(cakes[i - 1])

for p in xrange(2, P + 1):
for i in xrange(1, N + 1):
dp[p][i] = getArea(cakes[i - 1]) / p
for j in xrange(1, P + 1):
dp[p][i] = max(min(dp[p - j][i - 1], getArea(cakes[i - 1]) / j), dp[p][i])

return dp[P][N]

print getMaxCake([ 1, 1, 1, 2, 2, 3], 6)
print getMaxCake([4, 3, 3], 3)
print getMaxCake([6, 7], 12)``````

Related: