Dada una array arr que representa los diferentes ángulos en los que se corta un círculo, la tarea es determinar el número mínimo de cortes adicionales necesarios para que el círculo se divida en partes iguales.
Nota: La array ya está ordenada en orden ascendente.
Ejemplos:
Entrada: arr[] = {0, 90, 180, 270}
Salida: 0
No se requieren más cortes ya que el círculo ya está dividido en cuatro partes iguales.
Entrada: arr[] = {90, 210}
Salida: 1
Se requiere un solo corte a 330 grados para dividir el círculo en tres partes iguales.
Enfoque: La idea es calcular el Máximo Común Divisor de todos los valores obtenidos con la diferencia consecutiva de dos elementos en la array para encontrar el mayor tamaño posible (para reducir el número de cortes requeridos) para una parte que el círculo puede tener dividido en.
- Primero almacene la diferencia absoluta de los primeros dos valores de la array en una variable llamada factor = arr[1] – arr[0] .
- Ahora recorra la array desde el índice 2 hasta N-1 y, para cada elemento, actualice el factor como factor = gcd(factor, arr[i] – arr[i-1]) .
- Luego, para el factor de actualización del último elemento = gcd(factor, 360 – arr[N-1] + arr[0]) .
- Finalmente, los cortes totales requeridos serán (360 / factor) – N .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the number of cuts
// required to divide a circle into equal parts
int Parts(int Arr[], int N)
{
int factor = Arr[1] - Arr[0];
for (int i = 2; i < N; i++) {
factor = __gcd(factor, Arr[i] - Arr[i - 1]);
}
// Since last part is connected with the first
factor = __gcd(factor, 360 - Arr[N - 1] + Arr[0]);
int cuts = (360 / factor) - N;
return cuts;
}
// Driver code
int main()
{
int Arr[] = { 0, 1 };
int N = sizeof(Arr) / sizeof(Arr[0]);
cout << Parts(Arr, N);
return 0;
}
Java
// Java implementation of above approach
import java.io.*;
class GFG {
// Recursive function to return gcd of a and b
static int __gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return __gcd(a-b, b);
return __gcd(a, b-a);
}
// Function to return the number of cuts
// required to divide a circle into equal parts
static int Parts(int Arr[], int N)
{
int factor = Arr[1] - Arr[0];
for (int i = 2; i < N; i++) {
factor = __gcd(factor, Arr[i] - Arr[i - 1]);
}
// Since last part is connected with the first
factor = __gcd(factor, 360 - Arr[N - 1] + Arr[0]);
int cuts = (360 / factor) - N;
return cuts;
}
// Driver code
public static void main (String[] args) {
int Arr[] = { 0, 1 };
int N = Arr.length;
System.out.println( Parts(Arr, N));
}
}
// This code is contributed by anuj_67..
Python 3
# Python 3 implementation of # above approach import math # Function to return the number # of cuts required to divide a # circle into equal parts def Parts(Arr, N): factor = Arr[1] - Arr[0] for i in range(2, N) : factor = math.gcd(factor, Arr[i] - Arr[i - 1]) # Since last part is connected # with the first factor = math.gcd(factor, 360 - Arr[N - 1] + Arr[0]) cuts = (360 // factor) - N return cuts # Driver code if __name__ == "__main__": Arr = [ 0, 1 ] N = len(Arr) print( Parts(Arr, N)) # This code is contributed # by ChitraNayal
C#
// C# implementation of above approach
using System;
class GFG
{
// Recursive function to return gcd of a and b
static int __gcd(int a, int b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return __gcd(a-b, b);
return __gcd(a, b-a);
}
// Function to return the number of cuts
// required to divide a circle into equal parts
static int Parts(int []Arr, int N)
{
int factor = Arr[1] - Arr[0];
for (int i = 2; i < N; i++) {
factor = __gcd(factor, Arr[i] - Arr[i - 1]);
}
// Since last part is connected with the first
factor = __gcd(factor, 360 - Arr[N - 1] + Arr[0]);
int cuts = (360 / factor) - N;
return cuts;
}
// Driver code
static void Main()
{
int []Arr = { 0, 1 };
int N = Arr.Length;
Console.WriteLine(Parts(Arr, N));
}
}
// This code is contributed by ANKITRAI1
PHP
<?php
// PHP implementation of above approach
// Recursive function to return
// gcd of a and b
function __gcd( $a, $b)
{
// Everything divides 0
if ($a == 0)
return $b;
if ($b == 0)
return $a;
// base case
if ($a == $b)
return $a;
// a is greater
if ($a > $b)
return __gcd($a - $b, $b);
return __gcd($a, $b - $a);
}
// Function to return the number of cuts
function Parts($Arr, $N)
{
$factor = $Arr[1] - $Arr[0];
for ($i = 2; $i < $N; $i++)
{
$factor = __gcd($factor, $Arr[$i] -
$Arr[$i - 1]);
}
// Since last part is connected
// with the first
$factor = __gcd($factor, 360 -
$Arr[$N - 1] + $Arr[0]);
$cuts = (360 / $factor) - $N;
return $cuts;
}
// Driver code
$Arr = array( 0, 1 );
$N = sizeof($Arr);
echo (Parts($Arr, $N));
// This code is contributed by ajit.
?>
Javascript
<script>
// Javascript implementation of above approach
// Recursive function to return gcd of a and b
function __gcd(a, b)
{
// Everything divides 0
if (a == 0)
return b;
if (b == 0)
return a;
// base case
if (a == b)
return a;
// a is greater
if (a > b)
return __gcd(a-b, b);
return __gcd(a, b-a);
}
// Function to return the number of cuts
// required to divide a circle into equal parts
function Parts(Arr, N)
{
var factor = Arr[1] - Arr[0];
for (var i = 2; i < N; i++) {
factor = __gcd(factor, Arr[i] - Arr[i - 1]);
}
// Since last part is connected with the first
factor = __gcd(factor, 360 - Arr[N - 1] + Arr[0]);
var cuts = (360 / factor) - N;
return cuts;
}
// Driver code
var Arr = [ 0, 1 ];
var N = Arr.length;
document.write( Parts(Arr, N));
</script>
Producción:
358
Complejidad de tiempo: O(N * log(min(a, b))), donde a y b son dos parámetros de gcd.
Espacio auxiliar: O(log(min(a, b)))
Publicación traducida automáticamente
Artículo escrito por Naman_Garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA