Target Count Divisible By K

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
16    
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
Previous
2-Array 2-Sum
Next
Race Overtaking
1
0
2
1
2
2
2
3
2
4
2
5
2
6
3
7
target=2
Step 1 / 5
Step 1:
Find First Occurrence of 2.
Focus: default
target=2