Collect balls

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
11 upvotes
Asked in companies
MicrosoftAmazon

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3
6
Sample Output 1:
3
5
Explanation for Sample Input 1:
For case 1:
Initially, the box contains 1 ball. First operation is resetting the counter from 0 to 1 and for next two consecutive operations, throw 1 ball in each operation. After a total of three operations, the box contains 3 balls.

For Case 2:
First operation is resetting the counter from 0 to 1. Second operation is throwing 1 ball. Third operation is resetting the counter to 2 and for next two consecutive operations, throw 2 balls in each operation. After a total of five operations, the box contains 6 balls.
There exists another order for operations as well, but the number of operations cannot be less than 5.
Sample Input 2:
3
1
10
9
Sample Output 2:
0
7
6
Hint

Can you do something with factors of 'N'?

Approaches (1)
Maths + Observation

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.
  • There can be one prime factor greater than sqrt(N); thus if N remains greater than 1, add it into 'ans'.
  • Return 'ans'.
Time Complexity

O(√N), where ‘N’ denotes number of desired balls in the box.

An optimal prime factorization algorithm costs sqrt() time complexity. Hence, overall time complexity becomes O(√N).

Space Complexity

O(1).

We are using constant space. Hence, overall space complexity becomes O(1).

Code Solution
(100% EXP penalty)
Collect balls
Full screen
Console