# Techgig semi final solution

This time, TechGig: Largest Tech Community | Tech News & Hackathons has provided very good question, which will take sometime to resolve it.

Let me explain the definition in simple manner.

6 ball can be divided by 3 and 2, but if you divided it by 2 then you can not further divide 3 to equal part, so you have to divide it by 3.

Now, you will have 3 group of 2 ball of each and move count will be 1.

You have to divide further to make it equal part.

So 2 will be divided in equal portion for 3 group and you will have 6 group of 1 ball and your move count is 3 and if you combine moves then your current final move will be: 3+1 = 4 and last join total ball count, which is 6 so your final answer will be 10

For 8 ball, answer will be 15

For 14 ball, answer will be 22

For 16 ball, answer will be 31

Now, Check my attempt, it is not fully giving desired result, but I will update this post further.

Quiz:

### Solution

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import math def primefactors(n): ans = n while (n%2==0): n =n//2 ans+=n for i in range(3,int(math.sqrt(n))+2,2): while(n%i==0): n=n//i ans+=n if n>2: ans+=1 return ans n= int(input()) l = list(map(int,input().strip().split(" "))) op = 0 for d in l: op+=primefactors(d) print(op)

Logic:

We have to solve this using binary methods.

It can only pass the test case, if any one know then please comment it.

• TechTok July 10, 2021 at 1:03 PM

Taking too much time for having to factorize very large numbers. Rest i think it's working fine.

from math import sqrt
N = int(input("Enter N "))
Ni = input("Enter Ni ")
Ni = [int(x) for x in Ni.strip().split()]
moves = N
lst = []
for i,j in enumerate(Ni):
lst.append([])
for x in range(j):
if j%(x+1) == 0:
lst[i].append(x+1)

def nmoves(arr):
sum = 0
for i in arr:
if i >= sqrt(arr[-1]) and i!=1:
sum += i
return(sum)

for i in lst:
moves += nmoves(i)
print(moves)