数组中的 hackerrank 异或

Question

我正在尝试解决 this 关于 hackerrank 的问题，我花了一段时间才弄明白。

诀窍在于异或的属性和数字在数组子集中出现的次数，其中 子集是连续的（请注意）。

所以如果我们有 1,2,3 子集将是：

1
1,2
1,2,3
2
2,3
3

索引i处的值在这些子集中出现的次数是(n-i)*(i+1)，可以看出1出现了(3-0)*(0+1) = 3次。 n是数组的长度。

第二个技巧是XOR如果我们取这个数字偶数次，它本身就是0，如果它出现奇数次，答案就是数字本身，这也是需要注意的重要事项是 XOR 操作是关联的。

问题要求我们对子集进行异或，然后对每个结果值取 XOR。

因此，我没有采用蛮力方法，而是计算了每个数字在数组中出现的次数，并检查它出现的次数是偶数次还是奇数次，但有 8 个测试用例通过，4 个失败。测试用例太长，无法调试或干燥运行。

我的问题是为什么4个测试用例失败了。这是 Java 代码。

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;    
public class J {       
    static int []arr=new int[100000];
    static int an;
    public static void main(String[] args)throws IOException {

        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        int t,i,j,n;String []s;            
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        t=Integer.parseInt(br.readLine());            
        int []ans=new int[t];
        for(i=0;i<t;++i)
        {
         n = Integer.parseInt(br.readLine());             
         s=br.readLine().split(" ");
         j=0;         an=0;
         for(String str:s)
          arr[j++]=Integer.parseInt(str);
         for(j=0;j<n;++j)
         {                    
             if(((j+1)*(n-j))%2==1)
              an=an^arr[j];         
         }
         ans[i]=an;
        }
        for(i=0;i<t;++i)
         System.out.println(ans[i]);    
    }    
}

Answer 1

原因是溢出

(j+1)*(n-j)

产品可能是 ~10^10，因为数组的总大小最大为 10^5。

因此您需要使用 long 来计算此产品。

我用这个虚拟更改测试了你的代码：

long a = j + 1;
long b = (n - j);

if((a*b)%2==1) {
    an=an^arr[j]; 
}

并且程序成功通过了所有测试。

数组中的 hackerrank 异或

hackerrank xor in arrays

java

arrays

xor

data-structures