Nedbank Mock: Hidden Chip Detection (Q74)

[sudosf]

Problem

Given n square chips with side lengths and a factor k, find the maximum number of chips that can be hidden inside other chips. A chip can hide inside another if the larger side length >= k * smaller side length. Each chip is used in at most one pair.

Source

Nedbank VAS HackerRank Assessment - Q74
Tags: Easy, Sorting, Arrays, Two Pointers

References

• Related pattern: Pattern: Two Pointers (Arrays) #3

Constraints

• 1 <= n <= 2 * 10^5
• 1 <= imageDim[i] <= 10^9
• 1 <= k <= 10^9

Example

imageDim=[4,2,6,14], k=3
Output: 2  // 2->6 (2*3=6<=6), 4->14 (4*3=12<=14)

Approach Hints

• Sorting is a natural first step
• After sorting, think greedy: which chip should be matched to which?
• Two pointer approach from opposite ends of the sorted array
• Why is greedy matching from the middle outward suboptimal?

Complexity Target

• Time: O(n log n)
• Space: O(1) after sort

Notes

Language: Java
Watch for long overflow when computing k * imageDim[i] if k and imageDim values are both large.