【牛客编程巅峰赛S1第6场】牛牛爱奇数

题目

给定 n 个数，可以执行一种操作：每次选中一个偶数，然后把这些数中与该数相等的数都除以 2。例如现在有一个数组为 [2,2,3]，那么可以执行一次操作，使得这个数组变为[1,1,3]。
对于任意的 n 个数，最少需要操作多少次，使得这些数都变成奇数？

解题思路

对这 n 个数执行所有操作后，操作过程中出现多少种偶数（包括 a 中的偶数本身）即为所求。

遍历数组 a，如果该数是偶数且没有出现过，就累加一次计入答案。集合 st 记录当前已计算过的偶数。

C++代码

class Solution {
public:
    /**
     * 返回一个数，代表让这些数都变成奇数的最少的操作次数
     * @param n int整型 代表一共有多少数
     * @param a int整型vector 代表n个数字的值
     * @return int整型
     */
    int solve(int n, vector<int>& a) {
        // write code here
        int cnt = 0;
        set<int> st;
        for(auto i : a){
            while(i%2==0 && st.find(i)==st.end()){
                ++cnt;
                st.insert(i);
                i /= 2;;
            }
        }
        return cnt;
    }
};