时间戳

首页 > 解决方案 > 给定一个整数，你的任务是找到另一个整数，使得它们的按位异或最大

max - 给定一个整数，你的任务是找到另一个整数，使得它们的按位异或最大

问题描述

假设你有一个长度为 n 的数字的二进制表示为 x="0100" 并且任务是找到另一个数字 y=? 长度为 n 的 k 位应设置为使 x XOR y 最大。

例如：x="01010" 和 k=1 给定 o/p: y 应该是 10000

这是我的代码：但它不起作用..

 public static String maxXorValue(String x, int k) {
// Write your code here
    int arr[]=new int[x.length()];
    String ans="";
    for(int i=0;i<x.length();i++){
        arr[i]=Integer.parseInt(String.valueOf(x.charAt(i)));
    }
    if(k==0){
        return x;
    }
    else{
    int q=0;
    while(q<arr.length){
       if(k>0){
        if(arr[q]==0){
            k--;
            ans+="1";
            q++;
        }
        else{
            ans+="0";
            q++;
        }
    }
    else{
        ans+="0";
        q++;
    }
    
}
    return ans;
}

}

}

标签： maxxor

解决方案

算法

我找不到一个聪明的数学解决方案，而是一种（乏味的）计算答案的方法：

  1. 首先将候选解设为 y=0。设置num_bits_set为 0。
  2. （从左开始）在每个位值为x0 的位置，将该位置的值设置y为1并递增num_bits_set。num_bits_set==k如果在任何时候中断这一步
  3. 如果num_bits_set < k在完成步骤 (2) 后，取remaining=k-num_bits_set。从右边开始，在每个位值为x1 的位置，将该y位置的值也设置为 1 并递减remaining。如果在任何时候remaining==0中断此步骤
  4. 返回y

至于为什么会这样：

“1111...”（n 位）对于n位二进制数是最大的。假设启动那个y=0，那么x^y=x^0=x。

然后设置y导致 0 位x^y翻转为 1 的任何位增加x^y。让我们称其为“增加的变化” 设置y导致 1 位x^y翻转为 0 的任何位都会减少x^y。让我们称之为“减少变化”

我们使用贪心算法将k位设置为最大化x^y，首先按重要性降序检查所有“增加的变化”（首先取最大的增加，取第二大的第二等）。如果我们用完了增加的更改，我们开始进行减少的更改，但这次按重要性递增的顺序（即，如果您必须减少，则尽可能进行最小的更改x^y）。

由于所有位对总和的贡献都是独立的，因此这种贪心算法肯定会达到最佳结果。

例子

情况1

n = 5, k = 1
x = 01010, y = 00000, x^y=01010, num_bits_set = 0
# Start from the left, and every place where x = 0, set y=1 and increment num_bits_set
x = 01010, y = 10000, x^y=11010, num_bits_set = 1
    ^          ^
y = 10000
Done.

# y ^ x = 11010 Which is maximal

案例2

n = 5, k = 1
x = 01010, y = 00000, x^y=01010, num_bits_set = 0
# Start from the left, and every place where x = 0, set y=1 and increment num_bits_set
x = 01010, y = 10000, x^y=11010, num_bits_set = 1
    ^          ^
x = 01010, y = 10100, x^y=11110, num_bits_set = 2
      ^          ^
x = 01010, y = 10101, x^y=11111, num_bits_set = 3
        ^          ^
# num_bits_set < k, so continue with leftward pass
x = 01010, y = 10101, x^y=11111, remaining = 1
x = 01010, y = 10111, x^y=11101, remaining = 0
       ^          ^           
y = 10111
Done.

# y ^ x = 11101 which is maximal

如果您想实现这一点，我发现使用字符串比使用整数和旋转位更容易/更直观（但可能也更慢）。

推荐阅读