Dada una división de un círculo en n partes como una array de tamaño n. El i-ésimo elemento de la array denota el ángulo de una pieza. Nuestra tarea es hacer dos partes continuas a partir de estas piezas para que la diferencia entre los ángulos de estas dos partes sea mínima.
Ejemplos:
Input : arr[] = {90, 90, 90, 90}
Output : 0
In this example, we can take 1 and 2
pieces and 3 and 4 pieces. Then the
answer is |(90 + 90) - (90 + 90)| = 0.
Input : arr[] = {170, 30, 150, 10}
Output : 0
In this example, we can take 1 and 4,
and 2 and 3 pieces. So the answer is
|(170 + 10) - (30 + 150)| = 0.
Input : arr[] = {100, 100, 160}
Output : 40
Podemos notar que si una de las partes es continua, todas las partes restantes también forman una parte continua. Si el ángulo de la primera parte es igual a x, entonces la diferencia entre los ángulos de la primera y la segunda parte es |x – (360 – x)| = |2 * x – 360| = 2 * |x – 180|. Entonces, para cada parte continua posible, podemos contar su ángulo y actualizar la respuesta.
C++
// CPP program to find minimum
// difference of angles of two
// parts of given circle.
#include <bits/stdc++.h>
using namespace std;
// Returns the minimum difference
// of angles.
int findMinimumAngle(int arr[], int n)
{
int l = 0, sum = 0, ans = 360;
for (int i = 0; i < n; i++) {
// sum of array
sum += arr[i];
while (sum >= 180) {
// calculating the difference of
// angles and take minimum of
// previous and newly calculated
ans = min(ans, 2 * abs(180 - sum));
sum -= arr[l];
l++;
}
ans = min(ans, 2 * abs(180 - sum));
}
return ans;
}
// driver code
int main()
{
int arr[] = { 100, 100, 160 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMinimumAngle(arr, n) << endl;
return 0;
}
// This code is contributed by "Abhishek Sharma 44"
Java
// java program to find minimum
// difference of angles of two
// parts of given circle.
import java.util.*;
class Count{
public static int findMinimumAngle(int arr[], int n)
{
int l = 0, sum = 0, ans = 360;
for (int i = 0; i < n; i++)
{
// sum of array
sum += arr[i];
while (sum >= 180)
{
// calculating the difference of
// angles and take minimum of
// previous and newly calculated
ans = Math.min(ans,
2 * Math.abs(180 - sum));
sum -= arr[l];
l++;
}
ans = Math.min(ans,
2 * Math.abs(180 - sum));
}
return ans;
}
public static void main(String[] args)
{
int arr[] = { 100, 100, 160 };
int n = 3;
System.out.print(findMinimumAngle(arr, n));
}
}
// This code is contributed by rishabh_jain
Python3
#Python3 program to find minimum # difference of angles of two # parts of given circle. import math # function returns the minimum # difference of angles. def findMinimumAngle (arr, n): l = 0 _sum = 0 ans = 360 for i in range(n): #sum of array _sum += arr[i] while _sum >= 180: # calculating the difference of # angles and take minimum of # previous and newly calculated ans = min(ans, 2 * abs(180 - _sum)) _sum -= arr[l] l+=1 ans = min(ans, 2 * abs(180 - _sum)) return ans # driver code arr = [100, 100, 160] n = len(arr) print(findMinimumAngle (arr, n)) # This code is contributed by "Abhishek Sharma 44"
C#
// C# program to find minimum
// difference of angles of two
// parts of given circle.
using System;
class GFG
{
public static int findMinimumAngle(int []arr, int n)
{
int l = 0, sum = 0, ans = 360;
for (int i = 0; i < n; i++)
{
// sum of array
sum += arr[i];
while (sum >= 180)
{
// calculating the difference of
// angles and take minimum of
// previous and newly calculated
ans = Math.Min(ans,
2 * Math.Abs(180 - sum));
sum -= arr[l];
l++;
}
ans = Math.Min(ans,
2 * Math.Abs(180 - sum));
}
return ans;
}
// Driver code
public static void Main()
{
int []arr = { 100, 100, 160 };
int n = 3;
Console.WriteLine(findMinimumAngle(arr, n));
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP program to find minimum
// difference of angles of two
// parts of given circle.
// Returns the minimum difference
// of angles.
function findMinimumAngle($arr, $n)
{
$l = 0; $sum = 0; $ans = 360;
for ($i = 0; $i < $n; $i++)
{
// sum of array
$sum += $arr[$i];
while ($sum >= 180)
{
// calculating the difference of
// angles and take minimum of
// previous and newly calculated
$ans = min($ans, 2 *
abs(180 - $sum));
$sum -= $arr[$l];
$l++;
}
$ans = min($ans, 2 * abs(180 - $sum));
}
return $ans;
}
// Driver Code
$arr = array( 100, 100, 160 );
$n = sizeof($arr);
echo findMinimumAngle($arr, $n), "\n" ;
// This code is contributed by m_kit
?>
Javascript
<script>
// javascript program to find minimum
// difference of angles of two
// parts of given circle.
let MAXN = 109;
function findMinimumAngle(arr, n)
{
let l = 0, sum = 0, ans = 360;
for (let i = 0; i < n; i++)
{
// sum of array
sum += arr[i];
while (sum >= 180)
{
// calculating the difference of
// angles and take minimum of
// previous and newly calculated
ans = Math.min(ans,
2 * Math.abs(180 - sum));
sum -= arr[l];
l++;
}
ans = Math.min(ans,
2 * Math.abs(180 - sum));
}
return ans;
}
// Driver code
let arr = [ 100, 100, 160 ];
let n = 3;
document.write(findMinimumAngle(arr, n));
</script>
Producción :
40
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por Sagar Shukla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA