2025-10-18 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's October LeetCoding Challenge with cpp.

October LeetCoding Challenge 18

Description

Maximum Number of Distinct Elements After Operations

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.

 

Example 1:

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

Output: 6

Explanation:

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

Explanation:

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

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 0 <= k <= 109

Solution

class Solution {
public:
  int maxDistinctElements(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    nums[0] -= k;
    int len = nums.size();
    for(int i = 1; i < len; ++i) {
      nums[i] = min(max(nums[i - 1] + 1, nums[i] - k), nums[i] + k);
    }
    sort(nums.begin(), nums.end());
    return unique(nums.begin(), nums.end()) - nums.begin();
  }
};

// Accepted
// 633/633 cases passed (147 ms)
// Your runtime beats 28.89 % of cpp submissions
// Your memory usage beats 87.94 % of cpp submissions (97.5 MB)
Algorithm