AlgoLounge

Maximum Number of Distinct Elements After Operations

medium

You are given an integer array nums and an integer k.

You are allowed to perform the following operation on each element of the array at most once:

  • Add an integer in the range [-k, k] to the element.

Return the maximum possible number of distinct elements in nums after performing the operations.

Examples

Example 1

Input:  nums = [1,2,2,3,3,4], k = 2
Output: 6

nums changes to [-1, 0, 1, 2, 3, 4] after performing operations on the first four elements.

Example 2

Input:  nums = [4,4,4,4], k = 1
Output: 3

By adding -1 to nums[0] and 1 to nums[1], nums changes to [3, 5, 4, 4].

Constraints

  • 1 <= nums.length <= 10⁵
  • 1 <= nums[i] <= 10⁹
  • 0 <= k <= 10⁹
TypeScript
Loading editor…
List of test cases (12)
Case 1
nums = [1,2,2,3,3,4]
k = 2
Case 2
nums = [4,4,4,4]
k = 1
Case 3
nums = [1]
k = 0
Case 4
nums = [1,1,1,1,1]
k = 0
Case 5
nums = [1,1,1,1,1]
k = 2
Case 6
nums = [1,2,3,4,5]
k = 0
Case 7
nums = [5,5,5,5,5,5,5]
k = 3
Case 8
nums = [10,20,30,40]
k = 5
Case 9
nums = [1,1,2,2,3,3,4,4,5,5]
k = 1
Case 10
nums = [100,100,100]
k = 1000000000
Case 11
nums = [7,7,7,7,7,7,7,7,7,7]
k = 5
Case 12
nums = [3,1,4,1,5,9,2,6,5,3,5]
k = 2