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

There are two large causes of slowness with this code.

Clearing an array is slower than clearing a set

The first problem is this line:

memoize= [-1 for i in range(1000000)]

this prepares 1 million integers and is executed for each of your 1000 test cases. A faster approach is to simply use a Python set to indicate which values have already been visited.

Unnecessary loop being executed

The second problem is this line:

if primes[data] == 1 and memoize[data-1] == -1:

If you have a prime number, and you have already visited this number, you actually do the slow loop searching for prime factors which will never find any solutions (because it is a prime).

Faster code

In fact, the improvement due to using sets is so much that you don't even need your prime testing code and the following code passes all tests within the time limit:

import math
n = int(input())
for i in range(n):
  memoize = set()
  count = 0
  n = int(input())
  queue = []
  queue.append((n, count))
  while len(queue):
    data, count = queue.pop(0)
    if data <= 1:
      if data==1:
        count += 1
      break   
    if data-1 not in memoize:
        memoize.add(data-1)
        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 div not in memoize:
          memoize.add(div)
          queue.append((div, count+1))
  print(count)