Techgig semi final solution

Ankur Ranpariya
3 Jul, 2021
1

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:

Jazzy and Cricket Balls (100 Marks)

Jazzy is good with bowling but is not good with studies. His mom wants him to focus on studies too and for this she has found an interesting way. She has brought N packets of balls which may or may not have the same number of balls in them. The balls in a packet are arranged in a linear manner and Jazzy wants to play with the balls.


She will give the balls to Jazzy only if he can tell the maximum number of moves required in which he can get to play with all the balls. There are few conditions though:

  1. In one move, Jazzy can divide the number of balls in the packet into an equal number of groups only.
    Example: Suppose there are 6 balls in the packet.
    Jazzy can divide this packet in 3 ways.

1. Two groups of 3 balls each. (3, 3)
2. Three groups of 2 balls each (2, 2, 2)
3. Six groups of 1 ball each.


Note: Dividing a single group into multiple groups of equal number is considered one move only.


  1. Jazzy can get to play with the balls when they are present as a single unit only and not in any group of size greater than 1. Also, getting to play with a ball is considered a move.

Example: In a group there are 2 balls, then Jazzy cannot play with them until he further divides them into single-single units.


  1. The length of all the packets/groups should always be an integer.


Example:

Number of Packets, N = 1
Number of balls in packet = 6



Jazzy only cares about playing with the balls and needs your help in finding the maximum number of moves. Can you help him?




Input Format

The first line of input consists of the number of packets, N.
The second line of input consists of N space-separated integers representing the number of balls in the packet (length of the packet), Ni

Constraints

1<= N <=100
1<= Ni <=10^12 (1e12)

Output Format

Print the required number of maximum moves to get to play with the balls.

Sample TestCase 1

Input
2
6 1
Output
11

Explanation

For 6 numbers of balls in a packet, 10 moves are required as explained above.

For 1 ball, only 1 move is required.


Total number of moves = 10 + 1 = 11


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.

Next Post Previous Post
1 Comments
  • TechTok
    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)

    Reply
Add Comment
comment url