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

January 10, 2021

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

Example,

Input: [3, 1, 9, 12, 23, 10, 12, 12, 15, 23, 14, 12, 15]

Output: 12, 23 and 15



Input: [2, 1, 4, 7, 5, 9, 7, 3, 4, 6, 8, 3, 0, 3]

Output: 4 and 7

 

So let’s see the logic to find all the even 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 an even occurring element 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 even 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 even occurring elements
// in given array
void printRepeatingEven(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 even
    // 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 even occurrence
        if (!(pos & mapElementFrequency))
        {
            // print the even occurring numbers
            printf(" %d ", arr[i]);

            // set 1 to avoid printing duplicates
            mapElementFrequency ^= pos;
        }
    }
}



int main()
{
    int arr[] = {3, 2, 1, 4, 7, 5, 9, 7, 3, 4, 6, 8, 3, 0};

    const int N = ARRAY_SIZE(arr);

    printRepeatingEven(arr, N);

    return 0;
}

Output:

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

Recommended Articles for you: