The Minimum Stability Factor of Array problem asks you to find the minimum value of the maximum prime factor across all elements, achieved by optimally dividing array elements. Each operation allows dividing an element by one of its prime factors. The "stability factor" is defined as the maximum prime factor present in the array after all operations, and you want to minimize it. This hard Minimum Stability Factor of Array coding problem combines number theory, segment trees, and greedy reasoning.
Amazon asks this problem at senior engineering levels because it tests multi-domain expertise: number theory (prime factorization), binary search on the answer (minimum possible stability factor), and segment trees for efficient range queries. The array, math, number theory, binary search, and segment tree interview pattern is comprehensively tested, making this a strong signal for candidates targeting system-critical or algorithmic engineering roles.
Binary search on the answer (the stability factor value) combined with a feasibility check. For a given target factor F, determine if every array element can be reduced so that its largest prime factor ≤ F. For each element, greedily divide out all prime factors > F; if the remaining value > 1 has a prime factor > F (not removable), it's infeasible. A segment tree supports efficient range updates and max queries during the greedy validation step.
Array: [12, 15, 8]. Prime factorizations: 12=2²×3, 15=3×5, 8=2³.
Hard problems combining multiple techniques require building each component independently before integrating. First, practice binary search on the answer. Then practice sieve-based prime factorization. Finally, practice segment trees for range-max queries. When you encounter a problem with this many components, outline the approach at a high level before coding anything — interviewers reward structured decomposition even if your implementation time runs short.
