Last Updated: 29 Nov, 2021
Collect balls
Moderate
Asked in companies
You have a machine that throws ping-pong balls and has a counter meter installed in it. Each time when the button is pressed to throw the balls, the machine throws the number of balls equal to the integer saved in its counter meter.
E.g., Let the counter be set to 5; when the throw button is pressed, the machine will throw 5 ping-pong balls and turn itself off. To throw more balls, you need to press that button again with/without resetting the counter.
You have a box in front of you and want to collect 'N' balls in it. To achieve this, you are going to perform some operations, where each operation can be one of the following types:
1. Reset the counter with the number of balls present in the box.
2. Press the throw button.
If initially the counter is set to 0 and the number of balls in the box is 1, find the minimum number of operations needed to collect exactly 'N' balls (first ball inclusive), assuming that all balls thrown by the machine are collected in the box.
Input Format:
The first line contains 'T', denoting the number of tests.
For each Test :
The only line contains one integer 'N', denoting the required number of balls in the box.
Output Format:
For each test, print one integer, denoting the minimum number of operations needed to collect exactly 'N' balls in the box.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints -
1 <= 'T' <= 10^3
1 <= 'N' <= 10^6
Time Limit: 1 sec
Approaches
Approach: Our desired answer is the sum of all prime factors of 'N'.
Let the resetting operation be denoted by 'R' and throw denoted by 'T'. It can be seen that consecutively performing two or more 'R' operations is just a waste of moves, as the counter remains the same.
So, any optimal order of operations will look like "RTTTRTTRTTTT….", i.e., each 'R' followed by one or more 'T's.
Let's break this order into groups: [RTTT, RTT, RTTTT, …. ], and size of groups be [s1, s2, s3, ….]. Initially, the box contains one ball; after performing the first group of operations, it will contain 's1' balls (1 initial ball + 's1' - 1 throw with counter = 1).
The same is followed for each group of operations; after performing the second group of operations, the box will contain s1 * s2 balls (s1 previous balls + 's2' - 1 throw with counter = s1).
Thus, the total number of balls in the box becomes (s1 * s2 * s3 * ....), and the number of operations becomes (s1 + s2 + s3 + ….).
If any 's' can be denoted as (s = p * q), it must be divided into 'p' and 'q' because the product remains the same, but p+q will be less than or equal to 's'.
We need (s1 * s2 * s3 * ….) to be exactly equal to 'N'. Hence our desired answer is the sum of all prime factors of 'N'.
Algorithm:
- Initialize 'ans' with 0.
- Iterate a for loop, i = 2 to sqrt(N), to find prime factors of 'N'.
- While 'i' divides N.
- N /= i.
- ans += i.
- While 'i' divides N.
- There can be one prime factor greater than sqrt(N); thus if N remains greater than 1, add it into 'ans'.
- Return 'ans'.