Dada una array de números enteros binarios, suponga que estos valores se mantienen en la circunferencia de un círculo a la misma distancia. Necesitamos saber si es posible dibujar un polígono regular usando solo 1 como vértices y, si es posible, imprimir el número máximo de lados que tiene ese polígono regular.
Ejemplo:
Input : arr[] = [1, 1, 1, 0, 1, 0] Output : Polygon possible with side length 3 We can draw a regular triangle having 1s as its vertices as shown in below diagram (a). Input : arr[] = [1, 0, 1, 0, 1, 0, 1, 0, 1, 1] Output : Polygon possible with side length 5 We can draw a regular pentagon having 1s as its vertices as shown in below diagram (b).
Podemos resolver este problema obteniendo una relación entre el número de vértices que puede tener un posible polígono y el número total de valores en la array. Deje que un posible polígono regular en el círculo tenga K vértices o K lados, entonces debería satisfacer dos cosas para ser la respuesta,
Si el tamaño de array dado es N, entonces K debe dividir N; de lo contrario, K vértices no pueden dividir N vértices de la misma manera para ser un polígono regular.
Lo siguiente es que debe haber uno en cada vértice del polígono elegido.
Después de los puntos anteriores, podemos ver que para resolver este problema necesitamos iterar sobre los divisores de N y luego verificar si cada valor de la array a la distancia del divisor elegido es 1 o no. Si es 1, entonces encontramos nuestra solución. Podemos iterar sobre todos los divisores en tiempo O(sqrt(N)) simplemente iterando de 1 a sqrt(N). Puedes leer más sobre eso aquí .
Implementación:
C++
// C++ program to find whether a regular polygon
// is possible in circle with 1s as vertices
#include <bits/stdc++.h>
using namespace std;
// method returns true if polygon is possible with
// 'midpoints' number of midpoints
bool checkPolygonWithMidpoints(int arr[], int N,
int midpoints)
{
// loop for getting first vertex of polygon
for (int j = 0; j < midpoints; j++)
{
int val = 1;
// loop over array values at 'midpoints' distance
for (int k = j; k < N; k += midpoints)
{
// and(&) all those values, if even one of
// them is 0, val will be 0
val &= arr[k];
}
/* if val is still 1 and (N/midpoints) or (number
of vertices) are more than two (for a polygon
minimum) print result and return true */
if (val && N/midpoints > 2)
{
cout << "Polygon possible with side length " <<(N/midpoints) << endl;
return true;
}
}
return false;
}
// method prints sides in the polygon or print not
// possible in case of no possible polygon
void isPolygonPossible(int arr[], int N)
{
// limit for iterating over divisors
int limit = sqrt(N);
for (int i = 1; i <= limit; i++)
{
// If i divides N then i and (N/i) will
// be divisors
if (N % i == 0)
{
// check polygon for both divisors
if (checkPolygonWithMidpoints(arr, N, i) ||
checkPolygonWithMidpoints(arr, N, (N/i)))
return;
}
}
cout << "Not possiblen";
}
// Driver code to test above methods
int main()
{
int arr[] = {1, 0, 1, 0, 1, 0, 1, 0, 1, 1};
int N = sizeof(arr) / sizeof(arr[0]);
isPolygonPossible(arr, N);
return 0;
}
Java
// Java program to find whether a regular polygon
// is possible in circle with 1s as vertices
class Test
{
// method returns true if polygon is possible with
// 'midpoints' number of midpoints
static boolean checkPolygonWithMidpoints(int arr[], int N,
int midpoints)
{
// loop for getting first vertex of polygon
for (int j = 0; j < midpoints; j++)
{
int val = 1;
// loop over array values at 'midpoints' distance
for (int k = j; k < N; k += midpoints)
{
// and(&) all those values, if even one of
// them is 0, val will be 0
val &= arr[k];
}
/* if val is still 1 and (N/midpoints) or (number
of vertices) are more than two (for a polygon
minimum) print result and return true */
if (val != 0 && N/midpoints > 2)
{
System.out.println("Polygon possible with side length " +
N/midpoints);
return true;
}
}
return false;
}
// method prints sides in the polygon or print not
// possible in case of no possible polygon
static void isPolygonPossible(int arr[], int N)
{
// limit for iterating over divisors
int limit = (int)Math.sqrt(N);
for (int i = 1; i <= limit; i++)
{
// If i divides N then i and (N/i) will
// be divisors
if (N % i == 0)
{
// check polygon for both divisors
if (checkPolygonWithMidpoints(arr, N, i) ||
checkPolygonWithMidpoints(arr, N, (N/i)))
return;
}
}
System.out.println("Not possible");
}
// Driver method
public static void main(String args[])
{
int arr[] = {1, 0, 1, 0, 1, 0, 1, 0, 1, 1};
isPolygonPossible(arr, arr.length);
}
}
Python3
# Python3 program to find whether a
# regular polygon is possible in circle
# with 1s as vertices
from math import sqrt
# method returns true if polygon is
# possible with 'midpoints' number
# of midpoints
def checkPolygonWithMidpoints(arr, N, midpoints) :
# loop for getting first vertex of polygon
for j in range(midpoints) :
val = 1
# loop over array values at
# 'midpoints' distance
for k in range(j , N, midpoints) :
# and(&) all those values, if even
# one of them is 0, val will be 0
val &= arr[k]
# if val is still 1 and (N/midpoints) or (number
# of vertices) are more than two (for a polygon
# minimum) print result and return true
if (val and N // midpoints > 2) :
print("Polygon possible with side length" ,
(N // midpoints))
return True
return False
# method prints sides in the polygon or print
# not possible in case of no possible polygon
def isPolygonPossible(arr, N) :
# limit for iterating over divisors
limit = sqrt(N)
for i in range(1, int(limit) + 1) :
# If i divides N then i and (N/i)
# will be divisors
if (N % i == 0) :
# check polygon for both divisors
if (checkPolygonWithMidpoints(arr, N, i) or
checkPolygonWithMidpoints(arr, N, (N // i))):
return
print("Not possiblen")
# Driver code
if __name__ == "__main__" :
arr = [1, 0, 1, 0, 1, 0, 1, 0, 1, 1]
N = len(arr)
isPolygonPossible(arr, N)
# This code is contributed by Ryuga
C#
// C# program to find whether
// a regular polygon is possible
// in circle with 1s as vertices
using System;
class GFG
{
// method returns true if
// polygon is possible
// with 'midpoints' number
// of midpoints
static bool checkPolygonWithMidpoints(int []arr, int N,
int midpoints)
{
// loop for getting first
// vertex of polygon
for (int j = 0; j < midpoints; j++)
{
int val = 1;
// loop over array values
// at 'midpoints' distance
for (int k = j; k < N; k += midpoints)
{
// and(&) all those values,
// if even one of them is 0,
// val will be 0
val &= arr[k];
}
/* if val is still 1 and
(N/midpoints) or (number
of vertices) are more than
two (for a polygon minimum)
print result and return true */
if (val != 0 && N / midpoints > 2)
{
Console.WriteLine("Polygon possible with " +
"side length " +
N / midpoints);
return true;
}
}
return false;
}
// method prints sides in the
// polygon or print not possible
// in case of no possible polygon
static void isPolygonPossible(int []arr,
int N)
{
// limit for iterating
// over divisors
int limit = (int)Math.Sqrt(N);
for (int i = 1; i <= limit; i++)
{
// If i divides N then i
// and (N/i) will be divisors
if (N % i == 0)
{
// check polygon for
// both divisors
if (checkPolygonWithMidpoints(arr, N, i) ||
checkPolygonWithMidpoints(arr, N, (N / i)))
return;
}
}
Console.WriteLine("Not possible");
}
// Driver Code
static public void Main ()
{
int []arr = {1, 0, 1, 0, 1,
0, 1, 0, 1, 1};
isPolygonPossible(arr, arr.Length);
}
}
// This code is contributed by jit_t
PHP
<?php
// PHP program to find whether
// a regular polygon is possible
// in circle with 1s as vertices
// method returns true if polygon
// is possible with 'midpoints'
// number of midpoints
function checkPolygonWithMidpoints($arr, $N,
$midpoints)
{
// loop for getting first
// vertex of polygon
for ($j = 0; $j < $midpoints; $j++)
{
$val = 1;
// loop over array values
// at 'midpoints' distance
for ($k = $j; $k < $N; $k += $midpoints)
{
// and(&) all those values,
// if even one of them is 0,
// val will be 0
$val &= $arr[$k];
}
/* if val is still 1 and
(N/midpoints) or (number
of vertices) are more than
two (for a polygon minimum)
print result and return true */
if ($val && $N / $midpoints > 2)
{
echo "Polygon possible with side length " ,
($N / $midpoints) , "\n";
return true;
}
}
return false;
}
// method prints sides in
// the polygon or print not
// possible in case of no
// possible polygon
function isPolygonPossible($arr, $N)
{
// limit for iterating
// over divisors
$limit = sqrt($N);
for ($i = 1; $i <= $limit; $i++)
{
// If i divides N then
// i and (N/i) will be
// divisors
if ($N % $i == 0)
{
// check polygon for
// both divisors
if (checkPolygonWithMidpoints($arr, $N, $i) ||
checkPolygonWithMidpoints($arr, $N, ($N / $i)))
return;
}
}
echo "Not possiblen";
}
// Driver Code
$arr = array(1, 0, 1, 0, 1,
0, 1, 0, 1, 1);
$N = sizeof($arr);
isPolygonPossible($arr, $N);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to
// find whether a regular polygon
// is possible in circle with 1s as vertices
// method returns true if polygon is possible with
// 'midpoints' number of midpoints
function checkPolygonWithMidpoints(arr, N, midpoints)
{
// loop for getting first vertex of polygon
for (let j = 0; j < midpoints; j++)
{
let val = 1;
// loop over array values at
// 'midpoints' distance
for (let k = j; k < N; k += midpoints)
{
// and(&) all those values,
// if even one of
// them is 0, val will be 0
val &= arr[k];
}
/* if val is still 1 and
(N/midpoints) or (number
of vertices) are more than
two (for a polygon
minimum) print result and return true */
if (val && parseInt(N/midpoints) > 2)
{
document.write(
"Polygon possible with side length " +
parseInt(N/midpoints) + "<br>"
);
return true;
}
}
return false;
}
// method prints sides in the polygon or print not
// possible in case of no possible polygon
function isPolygonPossible(arr, N)
{
// limit for iterating over divisors
let limit = Math.sqrt(N);
for (let i = 1; i <= limit; i++)
{
// If i divides N then i and (N/i) will
// be divisors
if (N % i == 0)
{
// check polygon for both divisors
if (checkPolygonWithMidpoints(arr, N, i) ||
checkPolygonWithMidpoints(arr, N,
parseInt(N/i)))
return;
}
}
document.write("Not possible");
}
// Driver code to test above methods
let arr = [1, 0, 1, 0, 1, 0, 1, 0, 1, 1];
let N = arr.length;
isPolygonPossible(arr, N);
</script>
Producción
Polygon possible with side length 5
Complejidad de tiempo: O(sqrt(N) 2 )
Espacio auxiliar: O(1)
Este artículo es una contribución de Aarti_Rathi y Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA