Skip to content

3012. Minimize Length of Array Using Operations 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int minimumArrayLength(vector<int>& nums) {
    // Let the minimum number in the array `nums` be x.
    // * If there exists any element nums[i] where nums[i] % x > 0, a new
    //   minimum can be generated and all other numbers can be removed.
    // * If not, count the frequency of x in `nums`. For each pair of x, a 0 is
    //   generated which cannot be removed. Therefore, the result will be
    //   (frequency of x + 1) / 2.
    const int minNum = ranges::min(nums);
    if (ranges::any_of(nums, [minNum](int num) { return num % minNum > 0; }))
      return 1;
    return (ranges::count(nums, minNum) + 1) / 2;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public int minimumArrayLength(int[] nums) {
    // Let the minimum number in the array `nums` be x.
    // * If there exists any element nums[i] where nums[i] % x > 0, a new
    //   minimum can be generated and all other numbers can be removed.
    // * If not, count the frequency of x in `nums`. For each pair of x, a 0 is
    //   generated which cannot be removed. Therefore, the result will be
    //   (frequency of x + 1) / 2.
    final int minNum = Arrays.stream(nums).min().getAsInt();
    if (Arrays.stream(nums).anyMatch(num -> num % minNum > 0))
      return 1;
    final int freq = (int) Arrays.stream(nums).filter(num -> num == minNum).count();
    return (freq + 1) / 2;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def minimumArrayLength(self, nums: list[int]) -> int:
    # Let the minimum number in the array `nums` be x.
    # * If there exists any element nums[i] where nums[i] % x > 0, a new
    #   minimum can be generated and all other numbers can be removed.
    # * If not, count the frequency of x in `nums`. For each pair of x, a 0 is
    #   generated which cannot be removed. Therefore, the result will be
    #   (frequency of x + 1) / 2.
    minNum = min(nums)
    if any(num % minNum > 0 for num in nums):
      return 1
    return (nums.count(minNum) + 1) // 2