Coders Packet

Program to Identify Singleton element in a given array using JAVA

By Shiroli Nigam

Program to identify singleton (occurring once) elements in an array using JAVA programming.

Hi, in this project we will learn to write a program to identify singleton (occurring once) elements in an array. 

Logic

One way is to traverse the whole sorted array from the start. Now, as our array is sorted so we can find our target element easily. For this approach, the time complexity will be logarithmic (i.e. O(log n)). We will use Binary search for the given input array where all the elements that occur before the target element have an even index and the elements that occur after the target element will have an odd index.

1) Firstly we will create a function that will take an array and the index of endpoints of the array.

2) If the array is of size==1 we will return the element.

3) Then we will calculate the middle element and name it 'k'.

4) If the middle element (k) is even then we will compare the middle element with its next element. If both the elements are the same then the target element will come after the middle element and we will recursively call the function with the last element as the middle element (k).

5) If the middle element (k) is odd then we will compare the middle element with its previous element. If both the elements are the same then the target element will come before the middle element and we will recursively call the function with the first element as the middle+1 element (k+1).

public class Solution {

    public static int solve(int[] A, int i, int j) {
        if(i == j) {
            return A[i];
        }
        int k = i+(j-i)/2;
        if(A[2*(k/2)] != A[2*(k/2)+1]) {
            return solve(A, i, k);
        }else {
            return solve(A, k+1, j);
        }
    }

    public static void main(String[] args) {
        int[] A = {1, 1, 3, 3, 5, 5, 7, 7, 8, 9, 9, 10, 10}; 
System.out.print("\n\n The required element is: "); System.out.println(solve(A, 0, A.length-1)); } }

Output

output

Download project

Reviews Report

Submitted by Shiroli Nigam (shirolinigam)

Download packets of source code on Coders Packet