Given an array of binary integers, suppose these values are kept on the circumference of a circle at an equal distance. The task is to tell whether is it possible to draw a regular polygon using only 1s as its vertices or not.
If yes then print 1 else -1.
 
Example 1:
Input:
N=6
arr[] = { 1, 1, 1, 0, 1, 0 }
Output:  1
Explanation: 
Using 1's at 1st, 3rd and 5th index
we can make a triangle.
 
Example 2:
Input:
N=10
arr[] = { 1, 0, 1, 0, 1, 0, 1, 0, 1, 1 }
Output:  1
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function isPolygonPossible() that takes array arr and integer N as parameters and returns 1 if it is possible to make a regular polygon else -1.
 
Expected Time Complexity: O(N^{5}^{/2}).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 50

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def isPolygonPossible(self,arr, N) :
        #code here

Solutions:
import math

class Solution:

	def checkPolygonWithMidpoints(arr, N, midpoints):
		for j in range(midpoints):
			val = 1
			for k in range(j, N, midpoints):
				val &= arr[k]
			if val and N // midpoints > 2:
				return True
		return False

	def isPolygonPossible(self, arr, N):
		limit = math.sqrt(N)
		for i in range(1, int(limit) + 1):
			if N % i == 0:
				if Solution.checkPolygonWithMidpoints(arr, N, i) or Solution.checkPolygonWithMidpoints(arr, N, N // i):
					return 1
		return -1


class Solution:

	def checkPolygonWithMidpoints(self, arr, N, midpoints):
		for j in range(midpoints):
			val = 1
			for k in range(j, N, midpoints):
				val &= arr[k]
			if val and N // midpoints > 2:
				return True
		return False

	def isPolygonPossible(self, arr, N):
		limit = n ** 0.5
		for i in range(1, int(limit) + 1):
			if N % i == 0:
				if self.checkPolygonWithMidpoints(arr, N, i) or self.checkPolygonWithMidpoints(arr, N, N // i):
					return 1
		return -1


class Solution:

	def factorize(self, num):
		dividesN = []
		for i in range(3, num // 2 + 1):
			if num % i == 0:
				dividesN.append(i)
		if num >= 3:
			dividesN.append(num)
		return dividesN

	def check(self, arr, p):
		steplen = len(arr) // p
		for start in range(steplen):
			possible = True
			for a in range(start, len(arr), steplen):
				if arr[a] == 0:
					possible = False
					break
			if possible:
				return possible
		return False

	def isPolygonPossible(self, arr, N):
		possible_poly = self.factorize(N)
		for p in possible_poly:
			if self.check(arr, p):
				return 1
		return -1