Crea sito

Find the Number which occurs odd number of times

I’m practicing again with Algorithms and I’ve found an interesting Algorithmic Challenge named “Find the Number which occurs odd number of times in an Array”, so I have decided to try it and fortunately I solved it, but not without any problem.

I want to show you what the challenge exactly was and the code (first in Pseudocode, then in Java) to solve this problem.

Before starting I have to thank IDeserve for providing a lot of exercises about this topic.

THE PROBLEM:

In an array having positive integers, except for one number which occurs odd number of times, all other numbers occur even number of times. Find the number.
Example:
Input : 2 5 9 1 5 1 8 2 8
Output: 9

Input : 2 3 4 3 1 4 5 1 4 2 5
Output: 4

IDEA:

The first thing we note is that the array is not sorted and this could lead to a lot of complication, so the first operation is to sort it.

After the sort, we will have an ordered Array in ascending order, thus we can start thinking about a simple solution.

The main idea is to have two variables: currentNumber and times. In this two variables we will store the current number we are examining and the number of times it appears.

We set our current number as the first number in the array and the times as 1, because obviously it appears at least once since it is in the set.

Now, we start a for loop (int i is the iterator) from the second number (position 1 of index) and we create three if:

  • Only if we are at the end of the array and no one number was found, but we know that there has to be one number that appears odd times, then it is the case that the last number of the array is the one we were looking for.
  • If the number examined by the for loop IS equal to the previous number, then the currentNumber variable would be the same and the times that this number appears increases by 1.
  • If the number examined by the for loop IS NOT equal to the previous number, then, at first, if the variable times is not an even number, thus it is odd, it means the the previous number yet store in the currentNumber var. appears odd times. Since the currentNumber var. contains the number we were looking for. Thus we return this variable. But if the times of the previous number is even, no number is return, thus we continue or operation by saying that the currentNumber variable has to be changed and it would be equal to the examined number and the number of times return to 1.

 

PSEUDOCODE:

oddTimesNumber(A[]) {
    
    currentNumber = A[0]
    times = 1

    for(i = 1 to i < A.length) {

        if(i = A.length) {
            return A[i]
            }

        if(A[i] = A[i-1]) {
            currentNumber = A[i]
            times++
            }

        if(A[i] != A[i-1]) {
            if(times % 2 != 0) {
                return currentNumber
                }
            currentNumber = A[i]
            times = 1
            }

    }

    return currentNumber
}

JAVA:

public int oddTimesFinder(int[] A) {
		
		int currentNumber = A[0];
		int times = 1;
		
		for(int i = 1; i < A.length; i++) {
			
			if(i == A.length - 1) {
				return A[i];
			}
			
			if(A[i] == A[i-1]) {
				currentNumber = A[i];
				times++;
			}
			
			if(A[i] != A[i-1]) {
				if(times % 2 != 0) {
					return currentNumber;
				}
				
				currentNumber = A[i];
				times = 1;
				
			}
			
		}
		
		return 0;
	}

 

CONCLUSION:

The Algorithm is completed and it works for any input. Hope you understood it and for any question or correction comment below this post.

Don’t forget to follow me on Facebook, in the right bar of this page there is the Facebook Like Box for the official page of Big O Notation 🙂

See ya 😀