[LeetCode] 九坤-03. 数字默契考验

一、题目

某数学兴趣小组有 N 位同学，编号为 0 ~ N-1，老师提议举行一个数字默契小测试：首先每位同学想出一个数字，按同学编号存于数组 numbers。每位同学可以选择将自己的数字进行放大操作，每次在以下操作中任选一种（放大操作不限次数，可以不操作）：

将自己的数字乘以 2
将自己的数字乘以 3
若最终所有同学可以通过操作得到相等数字，则返回所有同学的最少操作次数总数；否则请返回 -1。

示例 1:

输入：numbers = [50, 75, 100]
输出：5
解释：
numbers[0] * 2 * 3 = 300 操作两次；
numbers[1] * 2 * 2 = 300 操作两次；
numbers[2] * 3 = 300 操作一次。共计操作五次。
1
2
3
4
5
6

示例 2:

输入：numbers = [10, 14]
输出：-1
解释：无法通过操作得到相同数字。
1
2
3

提示:

• 1 <= numbers.length <= 10^5
• 1 <= numbers[i] <= 10^9

二、题解

1. 任何一个数字都可以分解成 $x\ast 2^m\ast 3^n$；
2. 假如$number[i]$和$number[j]$可以通过乘以2或者乘以3变成相等的数字$num[k]$，根据1.有：
   $number[i]=num[i]\ast 2^{mi}\ast 3^{ni}$、$number[j]=num[j]\ast 2^{mj}\ast 3^{nj}$。
   那么有：$num[k]=num[i]\ast 2^{mi}\ast 3^{ni}\ast 2^{xi}\ast 3^{xj}=num[j]\ast 2^{mj}\ast 3^{nj}\ast 2^{xj}\ast 3^{xj}$，
   由于$num[i]$和$num[j]$都与2、3互质，因此为了满足上式，需要保证$num[i]=num[j]$。
3. 因此，我们可以将numbers中的所有数字分解为$num[i]\ast 2^{mi}\ast 3^{ni}$的形式，然后判断$num[0],num[1]...num[n-1]$是否相等，如果不相等返回$-1$。如果相等，再统计$2^m\ast 3^n$中2的幂次最大值$ma{x}_m$和3的幂次最大值$ma{x}_n$，需要乘以2或者乘以3的总次数就是各个数字的2的幂次变成$ma{x}_m$和3的幂次变成$ma{x}_n$的次数之和。
   具体请看下方代码

三、代码

class Solution {
public:
    // 把一个数字 分成 x *2*2*2*...*3*3*3， 返回{num[i], 2的幂次， 3的幂次}
    tuple<int, int, int> getAns(int num){
        int x = num;
        int cnt_2 = 0;
        int cnt_3 = 0;
        while(x%2==0){
            x/=2;
            cnt_2 ++;
        }
        while(x%3==0){
            x/=3;
            cnt_3 ++;
        }
        return {x, cnt_2, cnt_3};
    }
    
    int minOperations(vector<int>& numbers) {
        int ans = 0;
        int n = numbers.size();
        int a,b,c;
        vector<array<int, 3>> nums(n);
        for(int i=0; i<n; i++){
            tie(nums[i][0],nums[i][1],nums[i][2]) = getAns(numbers[i]);
        }
        for(int i=0; i<n-1; i++){
            if(nums[i][0]!=nums[i+1][0]){
                return -1;
            }
        }
        int max_cnt_2 = 0;
        int max_cnt_3 = 0;
        for(int i=0; i<n; i++){
            max_cnt_2 = max(max_cnt_2, nums[i][1]);
            max_cnt_3 = max(max_cnt_3, nums[i][2]);
        }
        for(int i=0; i<n; i++){
            ans += max_cnt_2 - nums[i][1];
            ans += max_cnt_3 - nums[i][2];
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

• 时间复杂度：O(n*log(n))；
• 空间复杂度：O(n*log(n))；