Codility PermMissingElem给出了奇怪的结果

Question

任务如下：

A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing. 
Your goal is to find that missing element. 
Write a function: 
class Solution { public int solution(int[] A); } 
that, given a zero-indexed array A, returns the value of the missing element. 
For example, given array A such that: 
    A[0] = 2 
    A[1] = 3 
    A[2] = 1 
    A[3] = 5 
the function should return 4, as it is the missing element. 
Assume that: 
N is an integer within the range [0..100,000]; 
the elements of A are all distinct; 
each element of array A is an integer within the range [1..(N + 1)]. 
Complexity: 
expected worst-case time complexity is O(N); 
expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments). 
Elements of input arrays can be modified. 

现在，我的解决方案如下：

// you can also use imports, for example: 
// import java.util.*; 

// you can use System.out.println for debugging purposes, e.g. 
// System.out.println("this is a debug message"); 

class Solution { 
    public int solution(int[] A) { 
     long nPlusOneSum = (A.length + 2) * (A.length + 1)/2; 
     long arraySum = 0; 
     for (int element : A) 
      arraySum += element; 
     return (int)(nPlusOneSum - arraySum); 
    } 
} 

的问题是，我有以下结果：

我不太明白为什么我有这些结果在large_range和large2测试中。

我犯了一个不大不小的考验自己应该模拟大阵：

import org.junit.Before; 
import org.junit.Test; 

public class SomeOtherTest { 
    int[] maxArray; 
    int N = 100000; 

    @Before 
    public void setUp() { 
     maxArray = new int[N]; 
     for (int i = 0; i < maxArray.length; i ++) { 
      maxArray[i] = i + 1; 
     } 
     maxArray[0] = maxArray.length + 1; 
    } 


    @Test 
    public void test() { 
     System.out.println(solution(maxArray)); 

    } 


    public int solution(int[] A) { 
     long nPlusOneSum = (A.length + 2) * (A.length + 1)/2; 
     long arraySum = 0; 
     for (int element : A) 
      arraySum += element; 
     return (int)(nPlusOneSum - arraySum); 
    } 
} 

，但它为我提供了正确的答案是1（使用JDK 1.8的东西，如codility）

链接试验结果：https://codility.com/demo/results/demoWAS9FA-5FA/

编辑：

这样的解决方案：

class Solution { 
    public int solution(int[] A) { 
     long nPlusOneSum = (A.length + 2) * (A.length + 1)/2; 
     for (int element : A) 
      nPlusOneSum -= element; 
     return (int)nPlusOneSum; 
    } 
} 

给出相同的结果：https://codility.com/demo/results/demoWAS9FA-5FA/

EDIT2

只要我引入临时变量来保存数组长度，测试通过 代码：

class Solution { 
    public int solution(int[] A) { 
     long numberOfElementsPlusOne = A.length + 1; 
     long nPlusOneSum = numberOfElementsPlusOne * (numberOfElementsPlusOne + 1)/2; 
     for (int element : A) 
      nPlusOneSum -= element; 
     return (int)nPlusOneSum; 
    } 
} 

结果：https://codility.com/demo/results/demoE82PUM-JCA/

EDIT3

的奇怪的是，测试仍然会产生正确的结果，甚至尽管它在评估期间，发生溢出。

nPlusOneSum得到溢出并获得值705182705而不是5000150001。

arraySum没有得到溢出，并在返回的语句获取的5000150000

然后值nPlusOneSum - arraySum进行评估，以-4294967295由于某种原因则是通过转化为(int)得到正确的价值1。

确切地说，当操作溢出它在java中的类型时会发生什么？

Answer 1

根据java的郎规格： http://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-15.17

类型的乘法表达的是提升的类型及其 操作数

所以所得两int乘法的类型也是一种int它在100.000左右默默溢出，解决办法是将操作数的类型改为long。

编辑

的奇怪的是，测试仍然会产生正确的结果，甚至尽管它在评估期间，发生溢出。

Answer 2

这里有一小部分，它的： 假设阵列的长度是100,000。您试图使用公式（N *（N + 1））/ 2来计算总和，即平均值（100,000 * 100,101）/ 2。所以这里它将两个数字相乘，这些数字已经超过了最大数据类型值。因此你已经看到了错误。

public int solution(int[] arr) { 
    int realLen = arr.length + 1; 
    long realSum = 0; 
    if(realLen%2 == 0) { 
     realSum = (realLen/2) * (realLen + 1); 
    } else { 
     realSum = realLen * ((realLen + 1)/2); 
    } 
    for(int i = 0; i < arr.length; i++) { 
     realSum = realSum - arr[i]; 
    } 

    return (int)realSum; 
} 

Answer 3

诀窍是A.length是整数。使用前应将其转换为long。

public int solution(int[] A) { 
    long sum = 0; 
    for (int element: A) { 
     sum += element; 
    } 

    long expectedSum = (((long) A.length + 1) * ((long) A.length + 2))/2; 

    return (int) (expectedSum - sum); 
}