You are given an array, arr of length N, and also a single integer K . Your task is to split the array arr into K non-overlapping, non-empty subarrays. For each of the subarrays, you calculate the sum of the elements in it. Let us denote these sums as S_{1},_{ }S_{2}, S_{3}, ..., S_{K}. Where S_{i }denotes the sum of the elements in the i^{th }subarray from left.
Let G = GCD( S_{1},_{ }S_{2 },S_{3 }, ...,_{ }S_{K}).
Find the maximum value of G that can be obtained. 
The array may contain duplicate elements.
Example 1:
Input:
N = 5
K = 4
arr[] = {6, 7, 5, 27, 3}
Output: 3
Explanation: 
Since K = 4, you have to split the array into 4 subarrays.
For optimal splitting, split the array into
4 subarrays as follows: [[6], [7, 5], [27], [3]]
Therefore, S_{1} = 6, S_{2} = 7 + 5 = 12, S_{3} = 27, S_{4} = 3
Hence, G = GCD(S_{1}, S_{2}, S_{3}, S_{4}) = GCD(6, 12, 27, 3) = 3
It can be shown that 3 is the maximum value of G that can be obtained.
Thus, the answer is 3.
Example 2:
Input:
N = 3
K = 2
arr[] = {1, 4, 5}
Output: 5
Explanation: 
Since K = 2, you have to split the array into 2 subarrays.
For optimal splitting, split the array into
2 subarrays as follows: [[1, 4], [5]]
Therefore, S_{1} = 1 + 4 = 5, S_{2} = 5
Hence, G = GCD(S_{1}, S_{2}) = GCD(5,5) = 5
It can be shown that 5 is the maximum value of G that can be obtained.
Thus, the answer is 5.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function solve() which takes the array arr[] and its size N and an integer K as input parameters and returns the required maximum GCD value.
 
Expected Time Complexity: O(N * x)
Expected Auxiliary Space: O(x), x is the number of factors of the sum of all elements.
Constraints:
1 <= N <= 10^{4}
1 <= K <= N
1 <= arr[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Mathematics

Starter code: 



from typing import List

class Solution:

    def solve(self, N : int, K : int, arr : List[int]) -> int:

        # code here

        



Solutions:
from typing import List
import math

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		a = sum(arr)
		d = []
		m = int(a ** 0.5)
		for i in range(1, m + 1):
			if a % i == 0:
				d.append(i)
				if i != a // i:
					d.append(a // i)
		d.sort(reverse=True)
		for i in range(1, N):
			arr[i] += arr[i - 1]
		out = 1
		for x in d:
			cnt = 0
			for y in arr:
				if y % x == 0:
					cnt += 1
			if cnt >= K:
				out = x
				break
		return out


from typing import List

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		for i in range(1, N):
			arr[i] += arr[i - 1]
		if K == 1:
			return arr[-1]
		max_sum = arr[-1]
		factors = []
		i = 1
		while i * i <= max_sum:
			if max_sum % i == 0:
				factors.append(i)
				if i != max_sum // i:
					factors.append(max_sum // i)
			i += 1
		factors.sort(reverse=True)
		for factor in factors:
			groups = 0
			for num in arr:
				if num % factor == 0:
					groups += 1
				if groups >= K:
					return factor
		return 1


from typing import List

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		s = sum(arr)
		for i in range(1, len(arr)):
			arr[i] += arr[i - 1]
		factors = []
		i = 1
		while i * i <= s:
			if s % i == 0:
				factors.append(i)
				if i != s / i:
					factors.append(s // i)
			i += 1
		factors.sort(reverse=True)
		ans = 1
		for i in factors:
			count = 0
			for j in arr:
				if j % i == 0:
					count += 1
			if count >= K:
				ans = i
				break
		return ans


from typing import List

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		pre_calc = list()
		for i in range(N):
			if i == 0:
				pre_calc.append(arr[i])
			else:
				pre_calc.append(arr[i] + pre_calc[i - 1])
		common = list()
		for i in range(1, pre_calc[-1] + 1):
			if i * i > pre_calc[-1]:
				break
			if pre_calc[-1] % i == 0:
				common.append(i)
				if i != pre_calc[-1] // i:
					common.append(pre_calc[-1] // i)
		answer = 0
		common.sort()
		common.reverse()
		for com in common:
			tmp_answer = 0
			for pre in pre_calc:
				if pre % com == 0:
					tmp_answer += 1
			if tmp_answer >= K:
				answer = max(answer, com)
				break
		return answer


from itertools import accumulate

class Solution:

	def solve(self, N, K, arr):
		(S, factors) = (sum(arr), set())
		for i in range(1, int(S ** 0.5) + 1):
			if S % i == 0:
				factors.add(i)
				factors.add(S // i)
		factors = sorted(factors, reverse=True)
		prefixsum = list(accumulate(arr))
		for i in factors:
			count = 0
			for j in prefixsum:
				count += not j % i
				if count >= K:
					return i


from typing import List

def solve(arr, n, k):
	total_sum = sum(arr)
	factors_total_sum = []
	for i in range(1, int(total_sum ** 0.5) + 1):
		if total_sum % i == 0:
			factors_total_sum.append(i)
			if total_sum // i != i:
				factors_total_sum.append(total_sum // i)
	factors_total_sum = list(sorted(factors_total_sum, reverse=True))
	prefix_sum = [arr[0]]
	for i in range(1, len(arr)):
		prefix_sum.append(prefix_sum[-1] + arr[i])
	for i in range(len(factors_total_sum)):
		c = k
		for j in range(len(prefix_sum)):
			if prefix_sum[j] % factors_total_sum[i] == 0:
				c -= 1
		if c <= 0:
			return factors_total_sum[i]
	return 1

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		return solve(arr, N, K)


from typing import List

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		for i in range(1, len(arr)):
			arr[i] += arr[i - 1]
		sum = arr[len(arr) - 1]
		i = 1
		new_l = []
		while i * i <= sum:
			if sum % i == 0:
				new_l.append(i)
				if sum // i != i:
					new_l.append(sum // i)
			i += 1
		new_l.sort(reverse=True)
		for n in new_l:
			c = 0
			for a in arr:
				if a % n == 0:
					c += 1
			if c >= K:
				return n
		return 1


import math
from typing import List

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		S = sum(arr)
		factors = []
		for i in range(1, int(math.sqrt(S)) + 1):
			if S % i == 0:
				factors.append(-i)
				factors.append(-S // i)
		presum = []
		s = 0
		for x in arr:
			presum.append(s + x)
			s += x
		for x in sorted(factors):
			cnt = 0
			for y in presum:
				if y % x == 0:
					cnt += 1
					if cnt >= K:
						break
			if cnt >= K:
				return -x


from typing import List

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		a = []
		total = sum(arr)
		for i in range(1, int(total ** 0.5) + 1):
			if total % i == 0:
				a.append(i)
				if i != total // i:
					a.append(total // i)
		a.sort(reverse=True)
		for i in range(1, N):
			arr[i] += arr[i - 1]
		for i in a:
			c = 0
			for j in arr:
				if j % i == 0:
					c += 1
				if c >= K:
					return i


from typing import List

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		total = sum(arr)
		factors = set()
		for i in range(1, int(total ** 0.5) + 1):
			if total % i == 0:
				factors.add(i)
				factors.add(total // i)
		for i in range(1, N):
			arr[i] += arr[i - 1]
		for factor in sorted(factors, reverse=True):
			c = 0
			for num in arr:
				if num % factor == 0:
					c += 1
			if c >= K:
				return factor
		return 1


from itertools import accumulate
from typing import List

class Solution:

	def solve(self, n: int, k: int, arr: List[int]) -> int:
		pref = list(accumulate(arr))
		div = set()
		ans = -1
		for i in range(1, int(pref[n - 1] ** 0.5) + 1):
			if pref[n - 1] % i == 0:
				div.add(i)
				div.add(pref[n - 1] // i)
		div = sorted(div, reverse=True)
		for it in div:
			c = 0
			for i in pref:
				if i % it == 0:
					c += 1
			if c >= k:
				return it


from typing import List

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		res = 1
		s = sum(arr)
		if K == 1:
			return s
		for i in range(1, N):
			arr[i] += arr[i - 1]
		for i in range(int(s ** 0.5), 1, -1):
			if s % i == 0:
				tmp = [i, s // i]
				for num in tmp:
					if num > res and num <= s // K:
						count = 0
						for nu in arr:
							if nu % num == 0:
								count += 1
						if count >= K:
							res = max(res, num)
		return res


from typing import List
import math

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		prefix_sum = [0] * N
		prefix_sum[0] = arr[0]
		for i in range(1, N):
			prefix_sum[i] = prefix_sum[i - 1] + arr[i]
		factor = [1]
		for i in range(2, int(math.sqrt(prefix_sum[-1])) + 1):
			if prefix_sum[-1] % i == 0:
				factor.append(i)
				if i != prefix_sum[-1] // i:
					factor.append(prefix_sum[-1] // i)
		if K == 1:
			return prefix_sum[-1]
		ans = 1
		factor
		for f in reversed(sorted(factor)):
			partition = 0
			for i in range(N):
				if prefix_sum[i] % f == 0:
					partition += 1
				if partition >= K:
					return f
		return ans


from typing import List

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		sm = sum(arr)
		facr = []
		j = 1
		while j * j <= sm:
			if sm % j == 0:
				facr.append(j)
				if j * j != sm:
					facr.append(sm // j)
			j += 1
		facr.sort(reverse=True)
		for fc in facr:
			cur = 0
			cnt = 0
			for i in range(N):
				cur += arr[i]
				if cur % fc == 0:
					cur = 0
					cnt += 1
			if cnt >= K:
				return fc


from typing import List

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		pre = [0 for i in range(N)]
		pre[0] = arr[0]
		for i in range(1, N):
			pre[i] += arr[i]
			pre[i] += pre[i - 1]
		f = []
		i = 1
		s = sum(arr)
		while i * i <= s:
			if s % i == 0:
				f.append(i)
				if s // i != i:
					f.append(s // i)
			i += 1
		f.sort(reverse=True)
		k = K
		for i in f:
			c = 0
			for j in pre:
				if j % i == 0:
					c += 1
			if c >= k:
				return i
		return 1


from typing import List

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		temp = []
		total = sum(arr)
		mid = int(total ** 0.5)
		for i in range(1, mid + 1):
			if total % i == 0:
				temp.append(i)
				if i != total // i:
					temp.append(total // i)
		temp.sort(reverse=True)
		for i in range(1, N):
			arr[i] += arr[i - 1]
		sol = 1
		for x in temp:
			freq = 0
			for y in arr:
				if y % x == 0:
					freq += 1
			if freq >= K:
				sol = x
				break
		return sol


from typing import List

class Solution:

	def solve(self, N: int, K: int, A: List[int]) -> int:
		for i in range(1, N):
			A[i] += A[i - 1]
		summ = A[-1]
		factors = []
		for i in range(1, int(summ ** 0.5) + 1):
			if summ % i == 0:
				factors.append(i)
				if summ // i != i:
					factors.append(summ // i)
		factors.sort(reverse=True)
		ans = 1
		for i in factors:
			c = 0
			for j in range(N):
				if A[j] % i == 0:
					c += 1
			if c >= K:
				return i
		return ans


from typing import List
from collections import Counter
import math

class Solution:

	def __init__(self):
		self.prime_numbers = {2: 1, 3: 1, 5: 1, 7: 1, 11: 1, 13: 1, 17: 1, 19: 1, 23: 1, 29: 1, 31: 1, 37: 1, 41: 1, 43: 1, 47: 1, 53: 1, 59: 1, 61: 1, 67: 1, 71: 1, 73: 1, 79: 1, 83: 1, 89: 1, 97: 1}
		self.pm_max = 97

	def is_prime(self, N):
		if N < self.pm_max:
			if N in self.prime_numbers:
				return 1
			return 0
		else:
			if n % 2 == 0 or n % 3 == 0:
				return 0
			limit = int(n ** 0.5)
			for i in range(5, limit + 1, 6):
				if N % i == 0 or N % (i + 2) == 0:
					return 0
			return 1

	def gcd(self, N, factors, __m):
		if N in __m:
			factors.extend(__m[N])
			return
		if self.is_prime(N):
			factors.append(N)
			return
		for p in self.prime_numbers:
			if N % p == 0:
				factors.append(p)
				if self.is_prime(N // p):
					factors.append(N // p)
					break
				else:
					self.gcd(N // p, factors, __m)
					break
		if not N in __m:
			__m[N] = factors

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		ssum = sum(arr)
		glist = []
		for i in range(1, math.ceil(math.sqrt(ssum))):
			if ssum % i == 0:
				glist.append(i)
				if ssum // i != i:
					glist.append(ssum // i)
		for j in range(1, N):
			arr[j] += arr[j - 1]
		glist.sort(reverse=True)
		ans = 1
		for j in range(len(glist)):
			c = 0
			for k in range(N):
				if arr[k] % glist[j] == 0:
					c += 1
				if c >= K:
					return glist[j]
		return 1


from typing import List

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		for i in range(1, N):
			arr[i] += arr[i - 1]
		facts = set()
		s = arr[N - 1]
		for i in range(1, int(s ** 0.5) + 1):
			if s % i == 0:
				facts.add(i)
				facts.add(s // i)
		facts = sorted(facts, reverse=True)
		res = 1
		sub = 0
		for fact in facts:
			count = 0
			for cur in arr:
				if (cur - sub) % fact == 0:
					count += 1
					sub = cur
			if count >= K:
				return fact
		return res


from math import gcd
from typing import List

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		s = sum(arr)
		a = int(s ** 0.5)
		for i in range(1, N):
			arr[i] += arr[i - 1]
		f = []
		for i in range(1, a + 1):
			if s % i == 0:
				f.append(i)
				if i != s // i:
					f.append(s // i)
		res = 1
		f.sort(reverse=True)
		for i in f:
			cnt = 0
			for x in arr:
				if x % i == 0:
					cnt += 1
			if cnt >= K:
				res = i
				break
		return res


from typing import List

class Solution:

	def solve(self, N: int, K: int, arr: List[int]) -> int:
		for i in range(1, N):
			arr[i] += arr[i - 1]
		su = arr[-1]
		(fact, i) = ([], 1)
		while i * i <= su:
			if su % i == 0:
				fact.append(i)
				if i != su // i:
					fact.append(su // i)
			i += 1
		fact.sort(reverse=True)
		answer = 1
		for i in fact:
			count = 0
			for k in arr:
				if k % i == 0:
					count += 1
			if count >= K:
				answer = i
				break
		return answer