title: Codility PermMissingElem gives strange results
body: <p>The task is the following:</p>
  
  <pre><code>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.
  </code></pre>
  
  <p>Now, my solution is the following:</p>
  
  <pre><code>// 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);
      }
  }
  </code></pre>
  
  <p>the problem is that i have the following results:</p>
  
  <p><img src="https://i.stack.imgur.com/bCfmA.png" alt="enter image description here"></p>
  
  <p>I don't quite understand why I'm having those results in <code>large_range</code> and <code>large2</code> tests.</p>
  
  <p>I made a sort of a test myself which should simulate large array:</p>
  
  <pre><code>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 &lt; 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);
      }
  }
  </code></pre>
  
  <p>but it provides me the correct answer which is <code>1</code> (used jdk 1.8 something as in codility)</p>
  
  <p>A link to the test results: <a href="https://codility.com/demo/results/demoWAS9FA-5FA/" rel="nofollow noreferrer">https://codility.com/demo/results/demoWAS9FA-5FA/</a></p>
  
  <p><strong>EDIT:</strong></p>
  
  <p>this solution:</p>
  
  <pre><code>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;
      }
  }
  </code></pre>
  
  <p>gives the same result: <a href="https://codility.com/demo/results/demoWAS9FA-5FA/" rel="nofollow noreferrer">https://codility.com/demo/results/demoWAS9FA-5FA/</a></p>
  
  <p><strong>EDIT2</strong></p>
  
  <p>as soon as I introduced temporary variable to hold array length, test passed
  code:</p>
  
  <pre><code>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;
      }
  }
  </code></pre>
  
  <p>result: <a href="https://codility.com/demo/results/demoE82PUM-JCA/" rel="nofollow noreferrer">https://codility.com/demo/results/demoE82PUM-JCA/</a></p>
  
  <p><strong>EDIT3</strong></p>
  
  <p>the weird thing is that test still produces correct results, even despite that during it evaluation, overflow occurs.</p>
  
  <p><code>nPlusOneSum</code> gets overflowed and gets value <code>705182705</code> instead of <code>5000150001</code>.</p>
  
  <p><code>arraySum</code> doesn't get overflowed and gets value of <code>5000150000</code></p>
  
  <p>Then at return statement <code>nPlusOneSum - arraySum</code> is evaluated to <code>-4294967295</code> which for some reason is then by conversion to <code>(int)</code> gets the correct value <code>1</code>.</p>
  
  <p>What happens exactly when operation overflows it's type in java?</p>