Проблема Hackerearth: бесконечные циклы рекурсии [closed]

Рассмотрим массив A размера N. Вы начинаете с индекса 0 и ваша цель – достичь индекса ровно за M ходов.

При любом индексе вы можете двигаться вперед или назад на количество шагов, равное простому делителю значения, которое существует в этом индексе. Вы не можете выйти за пределы массива при движении вперед или назад.

Напишите программу, чтобы определить, можно ли достичь индекса за M ходов.

Формат ввода

First line: T (number of test cases)
First line in each test case: N
Second line in each test case: N space-separated integers (denoting the array A)
Third line in each test case: M

Формат вывода

For each test case, print YES or NO depending upon the result.

Вот мой код

import math

def primeFactors(n): 
    arr = []
    while n % 2 == 0: 
        if(2 not in arr):
            arr.append(-2), 
            arr.append(2),
        n = n / 2
    for i in range(3,int(math.sqrt(n))+1,2): 
        while n % i== 0: 
            print (i), 
            if(i not in arr):
                arr.append(i),
                arr.append(-i),
            n = n / i 
    if n > 2: 
        if(n not in arr):
            arr.append(n)
            arr.append(-n)
    arr.sort(reverse = True)
    return arr

def check_path(N, A, M, idx):
    if(M == 0 and idx==N-1):
        return True
    arr = primeFactors(A[idx])
    #print('Prime Arr' + str(arr))
    for i in range(len(arr)):
        if(idx + arr[i]>0 and idx + arr[i]<N):
            #print('Curr idx: '+str(idx + arr[i]))
            if(check_path(N,A,M-1,idx+ arr[i])==True):
                return True
    return False

T = int(input()) for i in range(T):
    N = int(input())
    A = input().split(' ')
    M = int(input())
    for i in range(N):
        A[i] = int(A[i])
    if(check_path(N,A,M,0) == True):
        print("YES")
    else:
        print("NO")

Вывод для случая:

1 
6 
3 2 2 2 2 2 3

Должно быть “НЕТ”

Но я застрял в бесконечном рекурсивном цикле.

Заранее спасибо!

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *