Myntra Non-perfect-square Pairs

Learning Outcome

Turn the Myntra Non-perfect-square Pairs interview variant into a clear brute-force baseline, optimized pattern, and implementation plan.

Original Interview Statement

Given assigned numbers and at most k changes, maximize pairs whose product is not a perfect square.

Examples

Brute Force Approach

Compare every possible pair and try all changed values conceptually; this is not viable because changed values are unbounded.

Optimized Approach

Reduce every number to its square-free part. Equal square-free parts multiply to a perfect square, so the only bottleneck is the largest group after k removals.

Exact Pseudocode

squareFree each number
count frequencies
maxFreq = largest count
adjusted = max(0, maxFreq - k)
return min(n / 2, n - adjusted)
  

Reference Code

from collections import Counter

def square_free(x):
    res = 1
    p = 2
    while p * p <= x:
        cnt = 0
        while x % p == 0:
            cnt += 1
            x //= p
        if cnt % 2 == 1:
            res *= p
        p += 1
    if x > 1:
        res *= x
    return res

def get_nonperfect_pairs(arr, k):
    n = len(arr)
    freq = Counter(square_free(x) for x in arr)
    max_freq = max(freq.values(), default=0)
    adjusted = max(0, max_freq - k)
    return min(n // 2, n - adjusted)
  

Complexity

Edge Cases

• Perfect squares reduce to 1
• Large k
• Odd n
• All numbers in one group

Follow-ups

• What if changes have a cost?
• What if changed numbers must be from a fixed set?

Nearest Practice References

• Maximum matching in complete multipartite graph
• Square-free kernel
• Perfect square product property

Common Mistakes

• Copying the nearest LeetCode solution without checking the changed rule.
• Skipping duplicate or boundary cases.
• Not stating the brute force before the optimized approach.