Company: Harness__
Difficulty: medium
Problem Description You are given an array of elements where each element satisfies arr[i] < 10^6. You can take any two elements and pair them. A pair is considered to be a good pair if the product of the paired elements is not the square of any number. You are also given an integer k. You can perform operations on at most k elements, where an operation consists of changing an element's value to any other number. After performing at most k operations, find the maximum number of good pairs that can be formed. Examples Example 1 Input: arr = [2, 8], k = 0 Output: 0 Explanation: The product is 2 * 8 = 16, which is 4^2. Since the product is a perfect square, it is not a good pair. Example 2 Input: arr = [2, 8], k = 1 Output: 1 Explanation: We can change the value of the second element from 8 to 3. The pair becomes (2, 3). The product is 6, which is not a perfect square. Thus, it is a good pair. Constraints arr[i] < 10^6 The operations allow changing values to any number.