Down to zero| Queue
TASK(medium)
You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations on N in each move:
1: If we take 2 integers and where , , then we can change
2: Decrease the value of N by 1.
Determine the minimum number of moves required to reduce the value of N to 0.
Input Format
The first line contains the integer Q.
The next Q lines each contain an integer, N.
Constraints
1<=Q<=103
0<=N<=106
Output Format
Output lines. Each line containing the minimum number of moves required to reduce the value of N to 0.
Sample Input
2
3
4
Sample Output
3
3
SOLUTION 1
def downToZero(n):
# Write your code here
ops = 0
vals = [n]
while True:
newVals = []
for val in vals:
if val <= 3:
return ops + val
divisors = maxDivisors(val)
if divisors != []:
for div in divisors:
newVals.append(div)
newVals.append(val - 1)
ops += 1
vals = sorted(list(set(newVals)))
SOLUTION 2
def maxDivisors(n):
div = int(math.sqrt(n))
divisors = []
while div >= 2:
if n % div == 0:
divisors.append(int(n/div))
div -= 1
return divisors
EXPLANATION STEPS
1.Initialization:
- Use a queue (deque) to store tuples (num, moves) where num is the current number and moves is the number of operations taken to reach num.
- Use a visited set to keep track of visited numbers to avoid redundant calculations.
2.BFS Execution:
- Dequeue the current number num and moves count.
- If num is 0, return moves as it represents the minimum operations to reach zero.
- Perform two operations:
- Operation 1: Subtract 1 from num if num - 1 is non-negative and not visited.
- Operation 2: Divide num by each of its factors and enqueue resulting numbers if they are not visited.
- If num itself is a prime number greater than 1, enqueue 0 with moves + num because we can only subtract it to 0 directly.
3.Output:
- The function returns the minimum number of operations required to reduce N to 0 or -1 if it's not possible.
