Check if a key is present in every segment of size k in an array in Python

Suppose we have an array A with N elements, we have another value p and a segment size k, we have to check whether key p is present in every segment of size k in A.

So, if the input is like A = [4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4], p = 4 and k = 3, then the output will be True

To solve this, we will follow these steps −

• i := 0
• while i < n is non-zero, do
  • j := 0
  • while j < k, do
    • if arr[j + i] is same as p, then
      • break
    • j := j + 1
  • if j is same as k, then
    • return False
  • i := i + k
• if i is same as n, then
  • return True
• j := i - k
• while j < n, do
  • if arr[j] is same as p, then
    • break
  • j := j + 1
• if j is same as n, then
  • return False
• return True

Example

Let us see the following implementation to get better understanding −

 Live Demo

def key_in_segment_k(arr, p, k, n) :    i = 0    while i < n :       j = 0       while j < k :          if arr[j + i] == p :             break          j += 1       if j == k :          return False       i = i + k    if i == n :       return True    j = i - k    while j < n :       if arr[j] == p :          break       j += 1    if j == n :       return False    return True arr = [4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4] p, k = 4, 3 n = len(arr) print(key_in_segment_k(arr, p, k, n))

Input

[4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4]

Output

True