Given an array of elements where each element in the array represents the degree ( 0 <= a[i] <= 359 ) at which there is already a cut in a circle. The task is to find the minimum number of additional cuts required to make circle segments equal sized.
Examples:
Input : arr[] = { 0, 2 } Output : 178 Input : arr[] = { 30, 60, 180 } Output : 9
Approach : An efficient way to solve the above problem is to find gcd of all consecutive difference in angles. This gcd is the maximum angle of one circular segment and then the number of segments will be 360/gcdObtained. But, there are already N cuts. so additional cuts will be (360/gcdObtained) – N.
Below is the implementation of the above approach:
C++
// CPP program to find the minimum number // of additional cuts required to make // circle segments equal sized #include <bits/stdc++.h> using namespace std; // Function to find the minimum number // of additional cuts required to make // circle segments are equal sized int minimumCuts( int a[], int n) { // Sort the array sort(a, a + n); // Initial gcd value int gcd = a[1] - a[0]; int s = gcd; for ( int i = 2; i < n; i++) { gcd = __gcd(gcd, a[i] - a[i - 1]); s += a[i] - a[i - 1]; } // Including the last segment if (360 - s > 0) gcd = __gcd(gcd, 360 - s); return (360 / gcd) - n; } // Driver code int main() { int arr[] = { 30, 60, 180 }; int n = sizeof (arr) / sizeof (arr[0]); cout << minimumCuts(arr, n); return 0; } |
Java
// Java program to find the minimum // number of additional cuts required // to make circle segments equal sized import java.util.Arrays; class GFG { // Recursive function to // return gcd of two nos static int findgcd( int a, int b) { if (b == 0 ) return a; return findgcd(b, a % b); } // Function to find the minimum number // of additional cuts required to make // circle segments are equal sized static int minimumCuts( int a[], int n) { // Sort the array Arrays.sort(a); // Initial gcd value int gcd = a[ 1 ] - a[ 0 ]; int s = gcd; for ( int i = 2 ; i < n; i++) { gcd = findgcd(gcd, a[i] - a[i - 1 ]); s += a[i] - a[i - 1 ]; } // Including the last segment if ( 360 - s > 0 ) gcd = findgcd(gcd, 360 - s); return ( 360 / gcd) - n; } // Driver code public static void main(String[] args) { int [] arr = new int [] { 30 , 60 , 180 }; int n = arr.length; System.out.println(minimumCuts(arr, n)); } } // This code is contributed by mits |
Python 3
# Python 3 program to find the minimum number # of additional cuts required to make # circle segments equal sized import math # Function to find the minimum number # of additional cuts required to make # circle segments are equal sized def minimumCuts(a, n): # Sort the array a.sort() # Initial gcd value gcd = a[ 1 ] - a[ 0 ] s = gcd for i in range ( 2 ,n) : gcd = math.gcd(gcd, a[i] - a[i - 1 ]) s + = a[i] - a[i - 1 ] # Including the last segment if ( 360 - s > 0 ): gcd = math.gcd(gcd, 360 - s) return ( 360 / / gcd) - n # Driver code if __name__ = = "__main__" : arr = [ 30 , 60 , 180 ] n = len (arr) print (minimumCuts(arr, n)) |
C#
// C# program to find the minimum // number of additional cuts required // to make circle segments equal sized using System; class GFG { // Recursive function to // return gcd of two nos static int findgcd( int a, int b) { if (b == 0) return a; return findgcd(b, a % b); } // Function to find the minimum number // of additional cuts required to make // circle segments are equal sized static int minimumCuts( int []a, int n) { // Sort the array Array.Sort(a); // Initial gcd value int gcd = a[1] - a[0]; int s = gcd; for ( int i = 2; i < n; i++) { gcd = findgcd(gcd, a[i] - a[i - 1]); s += a[i] - a[i - 1]; } // Including the last segment if (360 - s > 0) gcd = findgcd(gcd, 360 - s); return (360 / gcd) - n; } // Driver Code static void Main() { int [] arr = new int [] { 30, 60, 180 }; int n = arr.Length; Console.WriteLine(minimumCuts(arr, n)); } // This code is contributed by ANKITRAI1 } |
PHP
<?php // PHP program to find the minimum // number of additional cuts required // to make circle segments equal sized // Recursive function to return // gcd of two nos function findgcd( $a , $b ) { if ( $b == 0) return $a ; return findgcd( $b , $a % $b ); } // Function to find the minimum number // of additional cuts required to make // circle segments are equal sized function minimumCuts( $a , $n ) { // Sort the array sort( $a ); // Initial gcd value $gcd = $a [1] - $a [0]; $s = $gcd ; for ( $i = 2; $i < $n ; $i ++) { $gcd = findgcd( $gcd , $a [ $i ] - $a [ $i - 1]); $s += $a [ $i ] - $a [ $i - 1]; } // Including the last segment if (360 - $s > 0) $gcd = findgcd( $gcd , 360 - $s ); return (360 / $gcd ) - $n ; } // Driver Code $arr = array (30, 60, 180); $n = sizeof( $arr ); echo (minimumCuts( $arr , $n )); // This code is contributed by ajit ?> |
Javascript
<script> // javascript program to find the minimum // number of additional cuts required // to make circle segments equal sized // Recursive function to // return gcd of two nos function findgcd(a , b) { if (b == 0) return a; return findgcd(b, a % b); } // Function to find the minimum number // of additional cuts required to make // circle segments are equal sized function minimumCuts(a, n) { // Sort the array a.sort(); // Initial gcd value var gcd = a[1] - a[0]; var s = gcd; for (i = 2; i < n; i++) { gcd = findgcd(gcd, a[i] - a[i - 1]); s += a[i] - a[i - 1]; } // Including the last segment if (360 - s > 0) gcd = findgcd(gcd, 360 - s); return (360 / gcd) - n; } // Driver code var arr = [ 30, 60, 180 ]; var n = arr.length; document.write(minimumCuts(arr, n)); // This code is contributed by aashish1995 </script> |
9
Time complexity: O(nlogn), since the sorting best algorithm takes (nlogn) times to sort the array.
Auxiliary Space: O(1), since no extra space has been taken.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!