AlgoVisual | See the logic

Given a sorted array of integers, arr, a target value, target, and a positive integer, k, return whether the number of occurrences of the target in the array is a multiple of k.

Example 1:

Input: arr = [1, 2, 2, 2, 2, 2, 2, 3], target = 2, k = 3
Output: True (2 occurs 6 times, 6 is a multiple of 3)

Example 2:

Input: arr = [1, 2, 2, 2, 2, 2, 2, 3], target = 2, k = 4
Output: False (6 is not a multiple of 4)

Example 3:

Input: arr = [1, 2, 2, 2, 2, 2, 3], target = 4, k = 3
Output: True (4 occurs 0 times, 0 is a multiple of any number)

1def isTargetCountDivisibleByK(arr: List[int], target: int, k: int) -> bool:

2 def findBound(isFirst):

3 l, r = 0, len(arr) - 1

4 res = -1

5 while l <= r:

6 mid = (l + r) // 2

7 if arr[mid] == target:

8 res = mid

9 if isFirst: r = mid - 1

10 else: l = mid + 1

11 elif arr[mid] < target:

12 l = mid + 1

13 else:

14 r = mid - 1

15 return res

17 first = findBound(True)

18 if first == -1: return 0 % k == 0

19 last = findBound(False)

20 count = last - first + 1

21 return count % k == 0

Target Count Divisible By K

Reference solution