Java program to find element that appears once

Software Development
#1

This is not an efficient approach but just another way to get the desired results. If we add each number once and multiply the sum by 2, we will get twice the sum of each element of the array. Then we will subtract the sum of the whole array from the twice_sum and get the required number (which appears once in the array).
Array [] : [a, a, b, b, c, c, d]
Mathematical Equation = 2*(a+b+c+d) – (a + a + b + b + c + c + d)

In more simple words: 2(sum_of_array_without_duplicates) – (sum_of_array)*

let arr[] = {7, 3, 5, 4, 5, 3, 4} Required no = 2*(sum_of_array_without_duplicates) - (sum_of_array) = 2*(7 + 3 + 5 + 4) - (7 + 3 + 5 + 4 + 5 + 3 + 4) = 2* 19 - 31 = 38 - 31 = 7 (required answer)

As we know that set does not contain any duplicate element we will be using the set.

Below is the implementation of above approach:

  • Java

// Java program to find

// element that appears once

import java.io.*;

import java.util.*;

class GFG

{

// function which find number

static int singleNumber( int [] nums, int n)

{

HashMap<Integer, Integer> m = new HashMap<>();

long sum1 = 0 , sum2 = 0 ;

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

{

if (!m.containsKey(nums[i]))

{

sum1 += nums[i];

m.put(nums[i], 1 );

}

sum2 += nums[i];

}

// applying the formula.

return ( int )( 2 * (sum1) - sum2);

}

// Driver code

public static void main(String args[])

{

int [] a = { 2 , 3 , 5 , 4 , 5 , 3 , 4 };

int n = 7 ;

System.out.println(singleNumber(a,n));

int [] b = { 15 , 18 , 16 , 18 , 16 , 15 , 89 };

System.out.println(singleNumber(b,n));

}

}

Output:

2 89

Another approach:

This is an efficient approach for finding the single element in a list of duplicate elements. In this approach, we are using binary search algorithm to find the single element in the list of duplicates elements.Before that, we need to make sure if the array is sorted. The first step is to sort the array because binary search algorithm wont work if the array is not sorted.

Now let us move to the binary search implementation:

There are two halfs that are created by the only single element present in the array which are left half and right half. Now if there are duplicates present in the left half, then the 1st instance of the duplicate element in the left half is an even index and the 2nd instance is an odd index. The opposite of the left half happens in the right half(1st instance is odd index and the second instance is even index). Now apply binary search algorithm:

1)The solution is to take two indexes of the array(low and high) where low points to array-index 0 and high points to array-index (array size-2). We take out the mid index from the values by (low+high)/2.

  1. Now check if the mid index value falls in the left half or the right half. If it falls in the left half then we change the low value to mid+1 and if it falls in the right half, then we change the high index to mid-1. To check it , we used a logic (if(arr[mid]==arr[mid^1]). If mid is an even number then mid^1 will be the next odd index , and if the condition gets satisfied, then we can say that we are in the left index,else we can say we are in the right half. But if mid is an odd index, then mid^1 takes us to mid-1 which is the previous even index , which is gets equal means we are in the right half else left half.

  2. This is done because the aim of this implementation is to find the single element in the list of duplicates. It is only possible if low value is more than high value because at that moment low will be pointing to the index that contains the single element in the array.

  3. After the loop ends, we return the value with low index.

  • Java

import java.io.*;

import java.util.Arrays;

class GFG{

static int singleelement( int arr[], int n)

{

int low = 0 , high = n - 2 ;

int mid;

while (low <= high)

{

mid = (low + high) / 2 ;

if (arr[mid] == arr[mid ^ 1 ])

{

low = mid + 1 ;

}

else

{

high = mid - 1 ;

}

}

return arr[low];

}

// Driver code

public static void main(String[] args)

{

int arr[] = { 2 , 3 , 5 , 4 , 5 , 3 , 4 };

int size = 7 ;

Arrays.sort(arr);

System.out.println(singleelement(arr, size));

}

}

Output:

2

The time complexity of the solution is O(N log(N))+O(log N) and its space complexity is O(1).