C program to find odd occurring elements in an array of limited range

In this blog post, we learn how to write a C program to find odd occurring elements in an array of limited range? So here we will write the C program to find odd occurring elements in an array of limited range. We will also see how to display the odd occurring elements in an array of limited range using C programming.

Example,

Input : arr = {1, 2, 3, 2, 3, 1, 3, 4, 4}
Output: 3

Explanation:

occurrence 1 > 2 times
occurrence 2 > 2 times
occurrence 3 > 3 times
occurrence 4 > 2 times

 

So let’s see the logic to find all the odd occurring elements in the given array. Suppose arr is an integer array of size N (arr[N] ), the task is to write the C program to find the odd occurring elements in an array.

 

Note: Here we assume that the size of the long long integer is 8 bytes (64 bit), so the below solution is capable to handle the array that elements are 0 to 63.

 

A simple solution would be to iterate the array elements and store frequency elements in a map. In the below function, I am using the ex-or operator to toggle the bit of map variable.

1 XOR 1 = 0
1 XOR 0 = 1
0 XOR 1 = 1
0 XOR 0 = 0

 

//function to create map for element frequency
long long mapElement(int arr[], const int n)
{
    long long mapElementFrequency = 0L;
    long long pos = 0L;
    int i =0;

    //iterate for each element
    for(i = 0; i < n; ++i)
    {
        //left-shift 1 by value of current element
        pos = 1 << arr[i];

        // Toggle the bit everytime element gets repeated
        mapElementFrequency ^= pos;
    }
    return mapElementFrequency;
}

 

Each 1 in the i’th index of the frequency mp represents the odd occurrence of element i. And each 0 in the i’th index represents even or non-occurrence of element i in the array.

 

If you want to learn more about the c language, here 10 Free days (up to 200 minutes) C video course for you.

Your free trial is waiting

 

C program to find odd occurring elements in an array of limited range:

 

#include<stdio.h>

//Calculate array size
#define ARRAY_SIZE(a)  sizeof(a)/sizeof(a[0])

//function to create map for element frequency
long long mapElement(int arr[], const int n)
{
    long long mapElementFrequency = 0L;
    long long pos = 0L;
    int i =0;
    //iterate for each element
    for(  i = 0; i < n; ++i)
    {
        //left-shift 1 by value of current element
        pos = 1 << arr[i];
        
        // Toggle the bit everytime element gets repeated
        mapElementFrequency ^= pos;
    }
    return mapElementFrequency;
}

// Function to find the odd occurring elements
// in given array
void printRepeatingOdd(int arr[], const int n)
{
    long long pos;
    int i =0;
    long long mapElementFrequency = mapElement(arr,n);
    
    // iterate array again and use mapElementFrequency to find odd
    // occurring elements
    for ( i = 0; i < n; ++i)
    {
        // left-shift 1 by value of current element
        pos = 1 << arr[i];

        // Each 0 in mapElementFrequency represents an odd occurrence
        if (pos & mapElementFrequency)
        {
            // print the odd occurring numbers
            printf(" %d ", arr[i]);
            // set 1 to avoid printing duplicates
            mapElementFrequency ^= pos;
        }
    }
}


int main()
{
    int arr[] = {1, 2, 3, 2, 3, 1, 3, 4, 4};

    const int N = ARRAY_SIZE(arr);

    printRepeatingOdd(arr, N);

    return 0;
}

Output:

C program to find odd occurring elements in an array of limited range1

 

Recommended Articles for you: