Dada una array de 
elementos donde cada elemento de la array representa el grado ( 0 <= a[i] <= 359 ) en el que ya hay un corte en un círculo. La tarea es encontrar el número mínimo de cortes adicionales requeridos para hacer segmentos circulares del mismo tamaño.
Ejemplos :
Input : arr[] = { 0, 2 }
Output : 178
Input : arr[] = { 30, 60, 180 }
Output : 9
Enfoque : una forma eficiente de resolver el problema anterior es encontrar el gcd de todas las diferencias consecutivas en los ángulos. Este mcd es el ángulo máximo de un segmento circular y luego el número de segmentos será 360/mcdObtenido. Pero, ya hay N cortes. entonces los cortes adicionales serán (360/gcdObtained) – N .
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
9
Complejidad de tiempo: O (nlogn), ya que el mejor algoritmo de ordenación tarda (nlogn) veces en ordenar la array.
Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA