Find the duplicate element in an array.

Approach: 

1. Add all the numbers in the array. And save it in a temp variable a. 
2. Solve mathematical formula n * (n+1)/2 where n is the length of array. Save it in another temp variable b.  
3. Duplicate integer = a - b 

This approach will only work if the integer is repeated only one. And if only one integer is repeated. 

Algorithm:

 Step 1: Declare and initialize an array ‘a’ of size 10 with the given values 1,2,3,4,5,6,7,8,9,9.

        0 1        2 3 4         5 6 7 8       9

1

2

3

4

5

6

7

8

9

9

Step 2: Declare a variable ‘sum1’ and initialize it to 0(zero) to store the sum of the given array. And assign n=10 (Number of array elements).

sum1 = 0

n = 10

Step 3: Declare a variable ‘sum’ to find and store sum (if there is no duplication) of array elements using a mathematical login n*(n+1)/2 (formula to find sum of sequence from 1 to n).

Here n = 10,

sum = 10 * (10 +1) / 2

sum = 10 * (11) / 2

sum = 110 / 2;

sum = 55.

Step 4: Using for loop, find sum of given array elements.

Iteration 1:

i = 0 and 0 < 10 -> Condition true

    0     1 2         3 4 5       6 7 8 9

1

2

3

4

5

6

7

8

9

9

sum1 = 0 + a[0] (sum1 = sum1 + a[i])

sum1 = 0 + 1

sum1 = 1

i = 1 (Incremented by one)

Iteration 2:

i = 1 and 1 < 10 -> Condition true

    0     1 2         3 4 5       6 7 8 9

1

2

3

4

5

6

7

8

9

9

sum1 = 1 + a[1]

sum1 = 1 + 2

sum1 = 3

i = 2 (Incremented by one)

Iteration 3:

i = 2 and 2 < 10 -> Condition true

    0     1 2         3 4 5       6 7 8 9

1

2

3

4

5

6

7

8

9

9

sum1 = 3 + a[2]

sum1 = 3 + 3

sum1 = 6

i = 3 (Incremented by one)

Iteration 4:

i = 3 and 3 < 10 -> Condition true

    0     1 2         3 4 5       6 7 8 9

1

2

3

4

5

6

7

8

9

9

sum1 = 6 + a[3]

sum1 = 6 + 4

sum1 = 10

i = 4 (Incremented by one)

Iteration 5:

i = 4 and 4 < 10 -> Condition true

    0     1 2         3 4 5       6 7 8 9

1

2

3

4

5

6

7

8

9

9

sum1 =10 + a[4]

sum1 = 10 + 5

sum1 = 15

i = 5 (Incremented by one)

Iteration 6:

i = 5 and 5 < 10 -> Condition true

    0     1 2         3 4 5       6 7 8 9

1

2

3

4

5

6

7

8

9

9

sum1 = 15 + a[5]

sum1 = 15 + 6

sum1 = 21

i = 6 (Incremented by one)

Iteration 7:

i = 6 and 6 < 10 -> Condition true

    0     1 2         3 4 5       6 7 8 9

1

2

3

4

5

6

7

8

9

9

sum1 = 21 + a[6]

sum1 = 21 + 7

sum1 = 28

i = 7 (Incremented by one)

Iteration 8:

i = 7 and 7 < 10 -> Condition true

    0     1 2         3 4 5       6 7 8 9

1

2

3

4

5

6

7

8

9

9

sum1 = 28 + a[7]

sum1 = 28 + 8

sum1 = 36

i = 8 (Incremented by one)

Iteration 9:

i = 8 and 8 < 10 -> Condition true

    0     1 2         3 4 5       6 7 8 9

1

2

3

4

5

6

7

8

9

9

sum1 = 36 + a[8]

sum1 = 36 + 9

sum1 = 45

i = 9 (Incremented by one)

Iteration 10:

i = 9 and 9 < 10 -> Condition true

    0     1 2         3 4 5       6 7 8 9

1

2

3

4

5

6

7

8

9

9

sum1 = 45 + a[9]

sum1 = 45 + 9

sum1 = 54

i = 10 (Incremented by one)

Iteration 11:

i = 10 and 10 < 10 -> Condition false

Terminate the loop.

Step 5: Declare a variable ‘dup’ to store the duplicate element.

dup = 10 - (55 - 54) (dup = n - (sum-sum1))

dup = 10 - 1

dup = 9.

So, the duplicate element in this given array is ‘9’.

Step 6: Print the duplicate element.

Dry run of sample output: 

Repeated Character: 9

Implementation:

include <iostream>

int main()

{

int a[10] = {1,2,3,4,5,6,7,8,9,9};

int sum1 = 0,n = 10;

int sum = n * (n+1) /2;

for(int i=0;i<n;i++)

{

sum1 = sum1 + a[i];

}

int dup = n - (sum-sum1);

std::cout<<"Repeated Character: "<<dup;

std::cin>>dup;

return 0;

}

Algorithm Complexity:

O(n)