Missing Number
Given an array ‘ARR’ of ‘N’ integers, where all the elements occur an even number of times and only one number occurs an odd number of times. Find the number which occurs an odd number of times.

EXAMPLE:

Input: 'N' = 5 'ARR' = 1 2 3 2 3 Output: 1 Except for number 1 all numbers occur even number of times.

Input Format :

The first line will contain integer 'T', the number of test cases. For each test case, there will be only two lines. The first line contains a single integer, 'N' representing the size of the array. The second line contains ‘N’ spaced integers.

Output format :

For each test case, print a single integer representing the number occurring odd number of times.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1

Question

Missing Number

Given an array ‘ARR’ of ‘N’ integers, where all the elements occur an even number of times and only one number occurs an odd number of times. Find the number which occurs an odd number of times.

EXAMPLE:

Input: 
'N' = 5
'ARR' = 1 2 3 2 3

Output: 1

Except for number 1 all numbers occur even number of times.

Input Format :

The first line will contain integer 'T', the number of test cases. For each test case, there will be only two lines.

The first line contains a single integer, 'N' representing the size of the array.
The second line contains ‘N’ spaced integers.

Output format :

For each test case, print a single integer representing the number occurring odd number of times.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 10
1 <= 'N' <= 10^4
1 <= ARR[i] <= 10^5
Time Limit: 1 sec

Accepted Answer

Calculate the sum of first n natural numbers as sumtotal= n*(n+1)/2
Create a variable sum to store the sum of array elements.
Traverse the array from start to end.
Update the value of sum as sum = sum + array[i]
Print the missing number as sumtotal - sum

Accepted Answer

Brute Force

Approach:

We will run two nested loops and count the occurrence of every element.

If at any moment, we are getting the count as odd, we will just print that element.

Algorithm :

For i = 0 to ‘N’
- Initialize ‘count’ variable as 0
- For j = 0 to ‘N’
  - If ‘ARR[j]’ is equal to ‘ARR[i]’
    - Increase ‘count’
- If the ‘count’ is odd return the ‘ARR[i]’

Space Complexity: O(1)Explanation:

O(1).

We are only using a single variable to store count, the space complexity will be O(1).

Time Complexity: O(n^2)Explanation:

O(N^2), Where ‘N’ size of the array.

As we are checking for each of the number in the array and for each check, we are again iterating the whole array to find the frequency, the time complexity will be O(N^2)

C++ (g++ 5.4)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(1)



    Where 'N' is the length of the array.

*/



int missingNumber(int n, vector &arr){

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



        // Store the count of arr[i].

        int count = 0;

        for(int j = 0; j < n; j++){

            if(arr[i] == arr[j]){

                count++;

            }

        }



        // If count is odd.

        if(count%2 != 0){

            return arr[i];

        }

    }

    return -1;

}

Python (3.5)

'''

    Time Complexity: O(N^2)

    Space Complexity: O(1)



    Where 'N' is the length of the array.

'''



from typing import *

    

def missingNumber(n, arr):

    for i in range(n):



        # Store the count of arr[i].

        count = 0;

        for j in range(n):

            if arr[i] == arr[j]:

                count += 1



        # If count is odd.

        if count%2 != 0:

            return arr[i]

    return -1;

Java (SE 1.8)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(1)



    Where 'N' is the size of the array.

*/



public class Solution {



    static int missingNumber(int n, int arr[]){

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

            // Store the count of arr[i].

            int count = 0;

            for(int j = 0; j < n; j++){

                if(arr[i] == arr[j]){

                    count++;

                }

            }



            // If count is odd.

            if(count%2 != 0){

                return arr[i];

            }

        }

        return -1;

    }

}

Accepted Answer

Hashing

Approach:

We will hash be using a hash data structure, so here we will store the frequency of an element ‘ARR[i]’ at ‘hash[ARR[i]]’.

Each time we encounter a number ARR[i] we will increase the value of hash[ARR[i]]

Algorithm :

Create a ‘hash[max(ARR[I])]’ array
For I = 0 to ‘N’
- Increase ‘hash[ARR[I]]’ by 1
For I = 0 to the maximum value in ‘ARR’ :
- If ‘hash[I]’ is odd
  - Return I

Space Complexity: O(n)Explanation:

O(max(ARR)), Where ‘ARR’ is the input array.

As we are using the extra ‘hash’ array of size ‘max[ARR[i]]’, the space complexity will be O(max(ARR)).

Time Complexity: O(n)Explanation:

O(N + max(ARR)), Where ‘N’ is the length of the array.

Only only iterating the array ‘ARR’ once and again iterating the array ‘hash’ once, so the time complexity will be O(N + max(ARR))

Python (3.5)

'''

    Time Complexity: O( N  )

    Space Complexity: O( N )



    Where 'N' is the size of an array.

'''



from typing import *

    

def missingNumber(n, arr):

    maxElement = 0;

    for i in range(n):

        maxElement = max(maxElement, arr[i]);

   

    hash = [0] * (maxElement + 1)

    for i in range(n):

        # Hashing.

        hash[arr[i]] += 1

   



    # Traversing the map 'mp'.

    for i in range(1, maxElement + 1):

        # If the frequency is odd.

        if hash[i]%2 != 0:

            return i

   

    return -1

C++ (g++ 5.4)

/*

    Time Complexity: O( N )

    Space Complexity: O( N )



    Where 'N' is the length of the array.

*/



int missingNumber(int n, vector &arr){



    int maxElement = 0;

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

        maxElement = max(maxElement, arr[i]);

    }

    vector hash(maxElement+1);

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



        // Hashing.

        hash[arr[i]]++;

    }



    // Traversing the map 'mp'.

    for(int i = 1; i <= maxElement; i++){



        // If the frequency is odd.

        if(hash[i]%2 != 0){

            return i;

        }

    }

    return -1;

}

Java (SE 1.8)

/*

    Time Complexity: O( N  )

    Space Complexity: O( N )



    Where 'N' is the length of the string.

*/



public class Solution {



    static int missingNumber(int n, int arr[]){



        int maxElement = 0;

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

            maxElement = Math.max(maxElement, arr[i]);

        }



        int hash[]=new int[maxElement+1];

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

            // Hashing.

            hash[arr[i]]++;

        }



        // Traversing the map 'mp'.

        for(int i = 1; i <= maxElement; i++){

            // If the frequency is odd.

            if(hash[i]%2 != 0){

                return i;

            }

        }



        return -1;

    }

}

Accepted Answer

Bitwise XOR

Approach:

The bitwise Xor all elements of the array where even occurring elements on Xor will give 0 whereas odd occurring element on xor give us the number since its even occurrence will give 0.

Algorithm :

Initialize a result ‘res’ variable as 0
For i = 0 to ‘N’
- ‘res = res XOR ARR[i]’
Return ‘res’

Space Complexity: O(1)Explanation:

O(1).

As we are using the extra ‘res’ variable, the space complexity will be O(1)

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ is the length of the array.

Only only iterating the array ‘ARR’ once, the time complexity will be O(N)

Python (3.5)

'''

    Time Complexity: O( N )

    Space Complexity: O( 1 )



    Where 'N' is the size of an array.

'''



from typing import *

    

def missingNumber(n, arr):

    # Store result.

    res = 0;

    for i in range(n):

        # Bitwise XOR.

        res = res ^ arr[i];

    return res

Java (SE 1.8)

/*

    Time Complexity: O( N )

    Space Complexity: O( 1 )



    Where 'N' is the size of the array.

*/



public class Solution {



    static int missingNumber(int n, int arr[]){

        // Store result.

        int res = 0;



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

            // Bitwise XOR.

            res = res ^ arr[i];

        }



        return res;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N)

    Space Complexity: O(1)



    Where 'N' is the length of the array.

*/



int missingNumber(int n, vector &arr){

    // Store result.

    int res = 0;

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



        // Bitwise XOR.

        res = res ^ arr[i];

    }

    return res;

}

Given an array ‘ARR’ of ‘N’ integers, where all the elements occur an even number of times and only one number occurs an odd number of times. Find the number which occurs an odd number of times.

EXAMPLE:

Input Format :

Output format :

Note :

Constraints :

Top Nagarro Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Nagarro Software Developer