钉钉 3.23 T2

钉钉 2.23 笔试第二题，朋友问我的，但是写出来不知道对不对，我感觉大概率对的，大家可以帮忙看看

对数组中任意两个元素一个除 2（向下取整），一个乘 2，问是否能把数组中元素置为同一个元素

思路是枚举最终相同数的二进制位长度，长度确定后去遍历数组内元素，都左移或右移到相同的长度，如果最后所有的数左移和右移后的数相等且最终左移和右移的位数和相同，则 Yes，其余情况为 No，时间复杂度最坏是 O(31 n)

int binary_length(int num) {
    int len = 0;
    while (num) {
        num >>= 1;
        ++len;
    }
    return len;
}

bool solution(vector<int> &nums) {
    int n = nums.size(), binary_len[n], max_binary_len = 0;
    for (int i = 0; i < n; ++i) {
        binary_len[i] = binary_length(nums[i]);
        max_binary_len = max(max_binary_len, binary_len[i]);
    }
    bool ans = false;
    // 枚举最终相同数的二进制位长度
    for (int i = 1; i < max_binary_len; ++i) {
        // 确定最终相同数的二进制长度后, 这个相同的数绝对是每一位左移或者右移得到的
        int same_num = binary_len[0] > i ? (nums[0] >> (binary_len[0] - i)) : (nums[0] << (i - binary_len[0]));
        int cnt = i - binary_len[0];
        bool can = true;
        for (int j = 1; j < n; ++j) {
            int num = binary_len[j] > i ? (nums[j] >> (binary_len[j] - i)) : (nums[j] << (i - binary_len[j]));
            if (same_num != num) {
                // 此时左移或右移到相同的二进制位数后仍然不相同, 所以直接 pass
                can = false;
                break;
            }
            cnt += i - binary_len[j];
        }
        if (can && cnt == 0) {
            // 这证明所有的数左移或右移后得到的数都是相同的, 且移动的位数和为0
            return true;
        }
    }
    return false;
}