C++ में सरणी में अद्वितीय तत्व जहां सभी तत्व k बार आते हैं सिवाय एक के

समस्या विवरण

हमारे पास एक सरणी A है। A में सभी तत्व m बार आते हैं, लेकिन एक तत्व केवल एक बार आता है। हमें उस अद्वितीय तत्व को ढूंढना है।

उदाहरण

यदि इनपुट A = [6, 2, 7, 2, 2, 6, 6], m = 3 है, तो आउटपुट 7 होगा।

एल्गोरिदम चरण

• INT_SIZE := एक पूर्णांक प्रकार के चर के आकार का 8 गुना
• आकार INT_SIZE का एक सरणी count परिभाषित करें और 0 से भरें
• i := 0 से INT_SIZE-1 तक लूप करें:
  • j := 0 से size-1 तक लूप करें:
    • यदि (arr[j] AND 2^i) != 0, तो count[i]++
  • res := 0
• i := 0 से INT_SIZE-1 तक लूप करें:
  • res := res + ((count[i] mod m) * 2^i)
• res वापस करें

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

int selectUnique(unsigned int arr[], int size, int m){
    int INT_SIZE = 8 * sizeof(unsigned int);
    int count[INT_SIZE];
    memset(count, 0, sizeof(count));
    for(int i = 0; i < INT_SIZE; i++)
        for(int j = 0; j < size; j++)
            if((arr[j] & (1 << i)) != 0)
                count[i] += 1;
    unsigned res = 0;
    for(int i = 0; i < INT_SIZE; i++)
        res += (count[i] % m) * (1 << i);
    return res;
}

int main(){
    unsigned int arr[] = { 6, 2, 5, 2, 2, 6, 6 };
    int size = sizeof(arr) / sizeof(arr[0]);
    int m = 3;
    cout << selectUnique(arr, size, m);
}

इनपुट

{ 6, 2, 5, 2, 2, 6, 6 }

आउटपुट

5