C++ में सिंगल नंबर III (Single Number III)

मान लीजिए हमारे पास एक सरणी (array) है जिसमें ठीक दो तत्व केवल एक बार आते हैं, जबकि बाकी सभी तत्व दो बार आते हैं। हमें एक फ़ंक्शन परिभाषित करना है जो इन दो संख्याओं को ढूंढे। उदाहरण के लिए, यदि दी गई सरणी [1,2,3,1,5,2] है, तो आउटपुट [3, 5] होगा।

हल करने के चरण

xor_res := 0 आरंभ करें।
सरणी के प्रत्येक तत्व के लिए xor_res := xor_res XOR nums[i] करें।
pos := 0 सेट करें।
जब xor_res AND (1 << pos) == 0 हो, तब pos को 1 से बढ़ाते रहें। यह पहला सेट बिट ढूंढता है।
num1 := 0 आरंभ करें।
फिर से सरणी को पार करें: यदि (nums[i] & (1 << pos)) != 0 हो, तो num1 := num1 XOR nums[i] करें।
num2 := xor_res XOR num1 की गणना करें।
num1 और num2 लौटाएं।

C++ उदाहरण

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

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xor_result = 0;
        for (int i = 0; i < nums.size(); i++) {
            xor_result ^= nums[i];
        }
        int pos = 0;
        while ((xor_result & (1 << pos)) == 0) {
            pos++;
        }
        int num1 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if ((nums[i] & (1 << pos)) != 0) {
                num1 ^= nums[i];
            }
        }
        int num2 = xor_result ^ num1;
        return {num1, num2};
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 2, 1, 3, 2, 5};
    print_vector(ob.singleNumber(v));
    return 0;
}

इनपुट

[1,2,1,3,2,5]

आउटपुट

[3, 5]