Kiểm tra số K có đủ để đi đến cuối mảng trong Python

Cho mảng nums và giá trị k. Duyệt mảng từ đầu đến cuối: nếu phần tử không phải số nguyên tố thì giảm k đi 1; nếu là số nguyên tố thì reset k về giá trị ban đầu. Kiểm tra xem có thể đến được chỉ số cuối cùng của mảng mà không để k ≤ 0 khi phần tử tiếp theo cũng không phải số nguyên tố.

Ví dụ: nums = [8,5,6,7,8], k = 2 → True.

Giải thuật

• Lưu temp = k.
• Duyệt mảng:
  • Nếu nums[i] là số nguyên tố → k = temp.
  • Ngược lại → k -= 1.
  • Nếu k <= 0 và chưa đến cuối mảng và phần tử tiếp theo không phải số nguyên tố → trả về False.
• Trả về True nếu duyệt hết.

Mã ví dụ

def isPrime(num):
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                return False
        return True
    return False

def solve(arr, k):
    temp = k
    for i in range(len(arr)):
        if isPrime(arr[i]):
            k = temp
        else:
            k -= 1
        if k <= 0 and i < (len(arr) - 1) and not isPrime(arr[i + 1]):
            return False
    return True

nums = [8, 5, 6, 7, 8]
k = 2
print(solve(nums, k))

Đầu vào

[8, 5, 6, 7, 8], 2

Đầu ra

True