Given an array of natural numbers count the sum of its proper divisors for every element in the array.
Example 1:
Input:
N = 3
arr = {2, 4, 3}
Output: {1, 3, 1}
Explaination: 
divisor of 2 is 1.
divisors of 4 is 1, 2.
divisor of 3 is 1.
Example 2:
Input:
N = 3
Arr = {2, 4, 1}
Output: {1, 3, 0}
Explaination: 
Proper divisor of 2 is 1.
Proper divisors of 4 is 1, 2.
Your Task:
You don't need to read input or print anything. Your task is to complete the function sumOfProperDivisors() which takes the array arr[] and its size N as input parameters and returns the sum of its proper divisors for every element in the array.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 100
1 ≤ arr[i] ≤ 100

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Mathematics

Starter code: #User function Template for python3
class Solution:
	def sumOfProperDivisors(self, arr, N):
		# code here


Solutions:
class Solution:

	def isprime(self, n):
		if n == 1:
			return False
		for i in range(2, int(n ** 0.5) + 1):
			if n % i == 0:
				return False
		return True

	def sumOfProperDivisors(self, arr, N):
		l = []
		for i in arr:
			c = 0
			if i == 0:
				c = 1
			for j in range(1, i):
				if i % j == 0:
					c += j
			l.append(c)
		return l


class Solution:

	def sumOfProperDivisors(self, arr, N):
		res = []
		for x in arr:
			if x == 1:
				res.append(0)
				continue
			temp = 1
			for i in range(2, x):
				if x % i == 0:
					temp += i
			res.append(temp)
		return res


class Solution:

	def sumOfProperDivisors(self, arr, N):
		ans = []
		for v in arr:
			a = 0
			if v == 0:
				a = 1
			for i in range(1, v):
				if v % i == 0:
					a += i
			ans.append(a)
		return ans


class Solution:

	def sumOfProperDivisors(self, arr, N):
		l = []
		s = 0
		for ele in arr:
			if ele == 1:
				l.append(0)
				continue
			if ele == 0:
				l.append(1)
				continue
			for i in range(1, ele):
				if ele % i == 0:
					s += i
			l.append(s)
			s = 0
		return l
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		arr = input().split()
		for itr in range(N):
			arr[itr] = int(arr[itr])
		ob = Solution()
		ans = ob.sumOfProperDivisors(arr, N)
		for i in range(len(ans)):
			print(ans[i], end=' ')
		print()


class Solution:

	def sumOfProperDivisors(self, arr, N):
		ma = max(arr)
		spf = [1 for i in range(ma + 1)]
		i = 2
		while i <= ma:
			j = i + i
			while j <= ma:
				spf[j] += i
				j += i
			i += 1
		ans = []
		for i in range(N):
			if arr[i] == 1:
				ans.append(0)
			elif arr[i] == 0:
				ans.append(1)
			else:
				ans.append(spf[arr[i]])
		return ans


class Solution:

	def sumOfProperDivisors(self, arr, N):
		l = []
		for i in arr:
			s = 0
			if i == 0:
				l.append(1)
			else:
				for p in range(1, i):
					if i % p == 0:
						s = s + p
				l.append(s)
		return l


class Solution:

	def sumOfProperDivisors(self, arr, N):

		def divisors(n):
			sum = 0
			if n == 0:
				return 1
			for i in range(1, n):
				if n % i == 0:
					sum += i
			return sum
		l = []
		for i in range(N):
			l.append(divisors(arr[i]))
		return l


import math

class Solution:

	def sumOfProperDivisors(self, arr, N):
		lis = []
		for i in arr:
			s = 0
			if i == 0:
				s = 1
			for j in range(1, i):
				if i % j == 0:
					s += j
			lis.append(s)
		return lis


class Solution:

	def sumOfProperDivisors(self, arr, N):
		c = []
		for i in arr:
			sum = 1
			if i == 1:
				c.append(0)
				continue
			a = 2
			while a * a <= i:
				if i % a == 0:
					sum = sum + a
					if a != i // a:
						sum = sum + i // a
				a = a + 1
			c.append(sum)
		return c


from math import sqrt

def fun2(n):
	if n == 0:
		return 1
	div2 = set()
	for i in range(1, int(sqrt(n)) + 1):
		if n % i == 0:
			div2.add(i)
			div2.add(n // i)
	n = len(div2)
	return sum(sorted(div2)[0:n - 1])

class Solution:

	def sumOfProperDivisors(self, arr, N):
		l = []
		for i in arr:
			l.append(fun2(i))
		return l


class Solution:

	def sumOfProperDivisors(self, arr, N):
		l1 = []
		for i in range(N):
			if arr[i] == 1:
				l1.append(0)
			else:
				sum = 1
				for j in range(2, arr[i]):
					if arr[i] % j == 0:
						sum += j
				l1.append(sum)
		return l1