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:
Recommended Articles for you:
- Best gift for programmers.
- Best electronic kits for programmers.
- C program to find even occurring elements in an array of limited range
- Find sum of all sub-array of a given array.
- C program to segregate even and odd numbers
- Find an element in array such that sum of left array is equal to sum of right array.
- C Program to find the count of even and odd elements in the array.
- Write C program to find the sum of array elements.
- Find the sum of array elements using recursion
- C Program to reverse the elements of an array
- C Program to find the maximum and minimum element in the array
- Calculate size of an array in without using sizeof in C
- How to create a dynamic array in C?
- How to access 2d array in C?
- Dangling, Void, Null and Wild Pointers
- Function pointer in c, a detailed guide
- How to use the structure of function pointer in c language?
- Memory Layout in C.
- 100 C interview Questions
- File handling in C.