求大神帮忙讲解一道OA的题

这是一道IBM的OA，写了半天也没有解出来，恳请哪位大神帮忙讲解一下，感谢感谢！

解出来了，感谢各位！！！

就是按2进制位分解，偶数位的1 count1，奇数位的1 count2，到4的余数部分count1（也可以先mod一下4然后用剩下的部分做第一步）。

第三个条件是说 所有的数对4的余数都是一样的
第二个条件说 原数组任何数减去余数后，如果写成二进制，1只会出现在偶数位

所以第一部找见数组里四的共同余数，应该有且只有一个，否则无解
第二步把所有数字都减去这个余数后，表示成二进制，统计下1都用了哪些位（2～16）

希望有帮助

我觉得可以这么想，将每个数看做它本身的二进制形式，这样在1，3，5... 位置上的1就是2的偶次方，然后2，4上的1是奇次方，奇次方可以是两个比他小的偶次方的和，除了0位置的1只能是1。这样应该是分解一个数的最优解。
如果有帮助，求加米~😄

可以当成4进制处理吗？ x = an*4^n + ... + a1 * 4 + a0  要求 a0 > 1, 然后 k-1 由前面 an ... a1 非零系数之和组成。

dfthb 发表于 2022-9-25 13:39
可以当成4进制处理吗？ x = an*4^n + ... + a1 * 4 + a0  要求 a0 > 1, 然后 k-1 由前面 an ... a1 非零系 ...

我是用二进制写的，下面是代码，可以参考一下。

class Solution {
    public static void main(String[] args) {
        int[] input = new int[]{5,1,4,6,10,21,70, 101};
        int size = input.length;
        int[] ans = new int[size];
        for(int i = 0; i < size; i++){
            ans[i] = helper(input[i]);
        }
        for(int n : ans){
            System.out.println(n);
        }
        
}
public static int helper(int num){
    if(num % 4 == 0){
        return -1;
    }
    if(num < 4){
        return 1;
    }
    num /= 4;
    String bin_num = Integer.toBinaryString(num);
    System.out.println("binary: " + bin_num);
    int counter = 0;
    boolean odd = true;
    char[] arr = bin_num.toCharArray();
    for(int i = arr.length - 1; i >= 0; i--){
        char c = arr[i];
        if(odd){
            counter += (c - '0');
        }
        else{
            counter += 2 * (c - '0');
        }
        odd = !odd;
    }
        return counter + 1;
    }
}

除以4，看商和余数：
1.余数为0，return -1 （因为没有小于4的数）；
2.余数>0, 商为0，k=1 (数本身<4，分解的是其本身)；
3.余数>0,商>0, 且商是偶数：k=2 (4^商 和余数）；
4.余数>0,商>0, 且商是基数：k=3 (4^(商-1), 4^(商-1),和余数）；