Skip to content

4005. Minimum Operations to Make Array Equal III πŸ”’

Description

You are given an integer array nums.

In one operation, you may choose any element nums[i] and perform one of the following:

  • Multiply nums[i] by an integer k, where k >= 2.
  • Divide nums[i] by an integer k, where 2 <= k < nums[i], provided that nums[i] is divisible by k.

Return the minimum number of operations required to make all elements of nums equal.

 

Example 1:

Input: nums = [6,12,8]

Output: 3

Explanation:

We can perform following operates to make all numbers to 6:

  • Divide nums[1] = 12 by 2 to get 6.
  • Divide nums[2] = 8 by 4 to get 2.
  • Multiply nums[2] = 2 by 3 to get 6.

Example 2:

Input: nums = [5,15,20]

Output: 2

Explanation:

We can perform following operates to make all numbers to 5:

  • Divide nums[1] = 15 by 3 to get 5.
  • Divide nums[2] = 20 by 4 to get 5.

Example 3:

Input: nums = [7,7,7]

Output: 0

Explanation:

All elements are already equal, so no operations are needed.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 10​​​​​​​9

Solutions

Solution 1

Thinking

With \(n\) up to \(10^5\) and values up to \(10^9\), we cannot simulate multiplications and divisions on every pair, nor test every reachable integer as a common target.

A single multiply or exact divide jumps a number to any multiple or proper divisor, so the cost of meeting at one target is governed by common factors and the extra factors each value must add or stripβ€”not by the number of intermediate integers.

We therefore compress each number by its factorization and accumulate the minimum operations over a candidate set far smaller than \(10^9\).

1


1


1


1

Comments