Down to zero problem - getting time exceeded error

Question

Trying to solve hackerrank problem.

You are given Q queries. Each query consists of a single number N. You can perform 2 operations on N in each move. If N=a×b(a≠1, b≠1), we can change N=max(a,b) or decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0.

I have used BFS approach to solve this.

a. Generating all prime numbers using seive

b. using prime numbers I can simply avoid calculating the factors

c. I enqueue -1 along with all the factors to get to zero.

d. I have also used previous results to not enqueue encountered data.

This still is giving me time exceeded. Any idea? Added comments also in the code.

import math
#find out all the prime numbers
primes = [1]*(1000000+1)
primes[0] = 0
primes[1] = 0
for i in range(2, 1000000+1):
  if primes[i] == 1:
    j = 2
    while i*j < 1000000:
      primes[i*j] = 0
      j += 1

n = int(input())
for i in range(n):
  memoize= [-1 for i in range(1000000)]
  count = 0
  n = int(input())
  queue = []
  queue.append((n, count))
  while len(queue):
    data, count = queue.pop(0)
    if data <= 1:
      count += 1
      break   
    #if it is a prime number then just enqueue -1
    if primes[data] == 1 and memoize[data-1] == -1:
      queue.append((data-1, count+1))
      memoize[data-1] = 1
      continue
    #enqueue -1 along with all the factors
    queue.append((data-1, count+1))
    sqr = int(math.sqrt(data))
    for i in range(sqr, 1, -1):
      if data%i == 0:
        div = max(int(data/i), i)
        if memoize[div] == -1:
          memoize[div] = 1
          queue.append((div, count+1))
  print(count)

Answer 1

Alternatively, there's a O(n*sqrt(n)) time and O(n) space complexity solution that passes all the test cases just fine.

The idea is to cache minimum counts for each non-negative integer number up to 1,000,000 (the maximum possible input number in the question) !!!BEFORE!!! running any query. After doing so, for each query just return a minimum count for a given number stored in the cache. So, retrieving a result will have O(1) time complexity per query.

To find minimal counts for each number (let's call it down2ZeroCounts), we should consider several cases:

1. 0 and 1 have 0 and 1 minimal counts correspondingly.
2. Prime number p doesn't have factors other than 1 and itself. Hence, its minimal count is 1 plus a minimal count of p - 1 or more formally down2ZeroCounts[p] = down2ZeroCounts[p - 1] + 1.
3. For a composite number num it's a bit more complicated. For any pair of factors a > 1,b > 1 such that num = a*b the minimal count of num is either down2ZeroCounts[a] + 1 or down2ZeroCounts[b] + 1 or down2ZeroCounts[num - 1] + 1.

So, we can gradually build minimal counts for each number in ascending order. Calculating a minimal count of each consequent number will be based on optimal counts for lower numbers and so in the end a list of optimal counts will be built.

To better understand the approach please check the code:

from __future__ import print_function

import os
import sys

maxNumber = 1000000
down2ZeroCounts = [None] * 1000001

def cacheDown2ZeroCounts():
    down2ZeroCounts[0] = 0
    down2ZeroCounts[1] = 1

    currentNum = 2
    while currentNum <= maxNumber:
        if down2ZeroCounts[currentNum] is None:
            down2ZeroCounts[currentNum] = down2ZeroCounts[currentNum - 1] + 1
        else:
            down2ZeroCounts[currentNum] = min(down2ZeroCounts[currentNum - 1] + 1, down2ZeroCounts[currentNum])

        for i in xrange(2, currentNum + 1):
            product = i * currentNum
            if product > maxNumber:
                break
            elif down2ZeroCounts[product] is not None:
                down2ZeroCounts[product] = min(down2ZeroCounts[product], down2ZeroCounts[currentNum] + 1)
            else:
                down2ZeroCounts[product] = down2ZeroCounts[currentNum] + 1    

        currentNum += 1

def downToZero(n):
    return down2ZeroCounts[n]

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    q = int(raw_input())

    cacheDown2ZeroCounts()
    for q_itr in xrange(q):
        n = int(raw_input())

        result = downToZero(n)

        fptr.write(str(result) + '\n')

    fptr.close()