public static int findDuplicate(int[] arr) {
    
    int n = arr.length-2;
    int sum = 0;
    for(int i : arr){
        sum =i;
    }
    
    return (sum - ((n*(n 1))/2));
}

Here is the code. This code must return any duplicate element present in the array. Say, if array is { 1, 2, 3, 4, 1 } then it must return 1. It works fine for the test cases but I just want to understand the role of arr.length-2 used here.

Sample input 5 size
1 2 3 4 1
Sample output :
1

CodePudding user response：

Your solution is based on assumption that your array must contain

• all numbers from 0 till "some" N, like 0, 1, 2, 3, .. , N (in any order)
• one extra number X (can be duplicate of other numbers, but doesn't need to be)

How many numbers are there in array?

• 0 ... N gives us N 1 numbers
• X is 1 number.

So we have N 1 1 which is N 2 numbers.

In other words array has N 2 numbers, which means N 2 = array.length.

And that means N = array.length - 2

(we will need that later).

Now sum of all numbers stored in array is 0 1 2 ... N X (their order doesn't matter).

We can get rid of 0 since it doesn't affect our sum, which gives us

SUM = 1   2   ...   N   X

We can also replace 1 2 ... N part with N*(N 1)/2 based on formula on sum of arithmetic series.

This leaves us with

SUM = N*(N 1)/2   X

Based on above the duplicate element X is X = SUM - N*(N 1)/2 where N = array.length-2.