Given an array arr[] denoting the radius of circular pizzas and an integer N denoting the number of friends. The task is to calculate the largest piece that can be cut from the pizzas such that every friend gets a piece of the pizza with the same area.
It is not allowed to make a slice from more than one pizza and each friend gets only one slice of pizza.
Example:
Input: arr[] = {1, 1, 1, 2, 2, 3}, N = 6.
Output: 7.0686
Explanation: Take the area of the pizza with a radius of 3, and divide by 4. (Area 28.743 / 4 = 7.0686). Use a similarly sized piece from the remaining pizza of radius 2 because total area of pizza with radius 2 are > 7.0686Input: arr[] = {6, 7}, N = 12
Output: 21.9911
Approach: This problem can be solved by using Binary Search. Follow the steps below to solve the given problem.
- Sort the array, this will help to use binary search on it.
- Now, the maximum area that the person can have is maxArea=π* a[n-1]*a[n-1] ( area of a circle – π*r2 ).
- Let the minimum area that the person can have be minArea=0.
- Now apply binary search on this given range.
- As π is constant so apply binary search from minArea=0 to maxArea= a[n-1]*a[n-1] and then after getting ( required radius * required radius ) through this binary search then multiply π into it.
- As the mid in the binary search can be in decimal as well so for that run a binary search for some number of iterations let’s say 500.
- We need to implement a possible function as well for the given mid of binary search.
- If that mid is valid for the problem that means the required answer is calculated and it is required to go to the right of binary search for the largest possible answer.
- If that mid is not valid for the problem that means all the answers to the right of that mid will also be not valid so go to the left.
- Now in isPossible() function, for each and every radius, check how many people can get pieces from that pizza, if the total people getting pizza >= given friends that means it is valid so go right in binary search else left.
- Print the answer found by doing the above operations.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to check if current distribution // is valid or not bool isPossible(double x, int a[], int n, int k) { for (int i = n - 1; i >= 0; i--) { int p = (a[i] * a[i]) / x; k -= p; if (k <= 0) return true; } if (k <= 0) return true; return false; } // Function to solve given problem long double maximumAreaPizza(int a[], int n, int k) { sort(a, a + n); double l = 0, r = a[n - 1] * a[n - 1]; int count = 500; double res = 0; while (count--) { double mid = double(l + r) / 2.0000; if (isPossible(mid, a, n, k)) { // cout << mid << " "; res = mid; l = mid; } else r = mid; } // After calculating radius*radius for // area multiply by pi(3.14) to get area long double p1 = res * 3.14159265359; return p1; } // Driver Code int main() { // Number of pizza int N = 6; // Radius of all pizzas int arr[] = { 1, 1, 1, 2, 2, 3 }; // Number of friends int K = 6; // Function Call cout << maximumAreaPizza(arr, N, K); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to check if current distribution // is valid or not static boolean isPossible(double x, int []a, int n, int k) { for (int i = n - 1; i >= 0; i--) { int p = (int)((a[i] * a[i]) / x); k -= p; if (k <= 0) return true; } if (k <= 0) return true; return false; } // Function to solve given problem static double maximumAreaPizza(int []a, int n, int k) { Arrays.sort(a); double l = 0, r = a[n - 1] * a[n - 1]; int count = 500; double res = 0; while (count > 0) { double mid = (double)(l + r) / 2.0000; if (isPossible(mid, a, n, k)) { // cout << mid << " "; res = mid; l = mid; } else r = mid; count--; } // After calculating radius*radius for // area multiply by pi(3.14) to get area double p1 = res * 3.14159265359; return p1; } // Driver Code public static void main(String args[]) { // Number of pizza int N = 6; // Radius of all pizzas int []arr = { 1, 1, 1, 2, 2, 3 }; // Number of friends int K = 6; // Function Call System.out.println(maximumAreaPizza(arr, N, K)); } } // This code is contributed by code_hunt. |
Python3
import math # Function to solve the given problem def maximumAreaPizza(radii, numberOfGuests): areas = [(math.pi) * r * r for r in radii] def isPossible(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 isPossible(x): l = x else: r = x return round(x, 4) # Driver Code arr = [ 1, 1, 1, 2, 2, 3] N = 6print(maximumAreaPizza(arr, N)) |
C#
using System; class GFG { // Function to check if current distribution // is valid or not static bool isPossible(double x, int []a, int n, int k) { for (int i = n - 1; i >= 0; i--) { int p = (int)((a[i] * a[i]) / x); k -= p; if (k <= 0) return true; } if (k <= 0) return true; return false; } // Function to solve given problem static double maximumAreaPizza(int []a, int n, int k) { Array.Sort(a); double l = 0, r = a[n - 1] * a[n - 1]; int count = 500; double res = 0; while (count > 0) { double mid = (double)(l + r) / 2.0000; if (isPossible(mid, a, n, k)) { // cout << mid << " "; res = mid; l = mid; } else r = mid; count--; } // After calculating radius*radius for // area multiply by pi(3.14) to get area double p1 = res * 3.14159265359; return p1; } // Driver Code public static void Main() { // Number of pizza int N = 6; // Radius of all pizzas int []arr = { 1, 1, 1, 2, 2, 3 }; // Number of friends int K = 6; // Function Call Console.Write(maximumAreaPizza(arr, N, K)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to check if current distribution // is valid or not function isPossible(x, a, n, k) { for (let i = n - 1; i >= 0; i--) { let p = Math.floor((a[i] * a[i]) / x); k -= p; if (k <= 0) return true; } if (k <= 0) return true; return false; } // Function to solve given problem function maximumAreaPizza(a, n, k) { a.sort(function (a, b) { return a - b }) let l = 0, r = a[n - 1] * a[n - 1]; let count = 500; let res = 0; while (count--) { let mid = (l + r) / 2.0000; if (isPossible(mid, a, n, k)) { res = mid; l = mid; } else r = mid; } // After calculating radius*radius for // area multiply by pi(3.14) to get area let p1 = res * 3.14159265359; return p1; } // Driver Code // Number of pizza let N = 6; // Radius of all pizzas let arr = [1, 1, 1, 2, 2, 3]; // Number of friends let K = 6; // Function Call document.write(maximumAreaPizza(arr, N, K).toPrecision(6)); // This code is contributed by Potta Lokesh </script> |
Output
7.06858
Time Complexity: O(N logN)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
