Find two numbers that occur only once in a set of numbers

What I want to share with you today is a relatively interesting programming problem that I have done recently. I hope it will be of benefit to you. Without further ado, let’s get to the point.

Simple version problem and solution

Given an array nums containing only integers, each element will appear twice and only one number will appear only once, find this unique number.

This is a simplified version of the problem to be explained today, which is to use finding the number that only appears once in a bunch of numbers that appear twice, is it a feeling of finding a single dog in a bunch of couples?

Before formally explaining the topic, let's first understand a unary operator - ^, XOR operation. The function of this operator is to operate on each bit under the binary of the two numbers. If the two numbers are the same (both are 1 or both are 0), then this bit of the result is 0, if this bit is the same If the two numbers are different (one is 1 and the other is 0), then this bit of the result is 1.

 

As shown in the figure, it is the result of the XOR operation. Each bit on a and b is the same, and the result becomes 0, otherwise it becomes 1.

Then we can understand one thing, if two identical numbers are XORed, then the result must be 0, because every bit of the two identical numbers must be the same.

We can also draw a conclusion that if 0 is XORed with any number, the result is still this number, because every bit of 0 is 0, if a certain bit of this number is zero, it will still be 0 after XOR with 0 , if it is 1, it is still 1 after the XOR.

Then we can easily get the solution to this problem, XOR all the numbers in the array, and the result is the result we want.

#include<stdio.h>
//find unique number
int singleNonDuplicate(int* parr,int nums)
{
    int ret = 0;
    int i = 0;
    //XOR each number in an array
    for (i = 0;i < nums;i++)
    {
        ret = ret ^ *(parr + i);
    }
    //output XOR result
    return ret;
}
int main()
{
    int arr[] = { 1,2,3,4,5,4,3,2,1,6,6 };
    int i = 0;
    int number1 = sizeof(arr) / sizeof(arr[0]);
    for (i = 0;i < number1;i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    printf("%d", singleNonDuplicate(arr, number1));
    return 0;
}

Deepen the difficulty

So let's take the first question a step further, what if we want to find two numbers in an array that only occur once?

XORing all arrays is obviously not advisable, it will only get a result where two numbers that appear only once are XORed with each other.

We need to disassemble the problem, divide an array into two arrays, and each of the two arrays contains two numbers that appear only once, and then keep your eyes open to see how it works.

split array

First, we need to XOR all the numbers. The final result is the XOR result of two numbers that appear only once. At this time, the bit of 1 in the binary bit of the result is the difference between the two numbers, that is, we can use This is the basis for the division to ensure that the two results we want will not be divided together.

XOR solution

Then, you can solve the second problem just like you solved the first problem.

attached code

#include<stdio.h>
//find unique numbers
void singleNonDuplicate(int* parr,int nums,int* pc)
{
    int temp = 0;
    int ret[2] = {0,0};
    int i = 0;
    int j = 0;
    //XOR each number in an array
    for (i = 0;i < nums;i++)
    {
        temp = temp ^ *(parr + i);
    }
    //Get the i-th bit as 1
    for (i = 0;i < 32;i++)
    {
        if (1&(temp >> i))
        {
            break;
        }
    }
    //Group XOR
    for (j = 0;j < nums;j++)
    {
        if (1 & (parr[j] >> i))
            ret[0] = ret[0] ^ parr[j];
        else
            ret[1] = ret[1] ^ parr[j];
    }
    
    *pc = ret[0];
    *(pc + 1) = ret[1];//output XOR result
}
int main()
{
    int arr[] = { 1,2,3,4,5,4,3,2,1,6,6,8};
    int i = 0;
    int number1 = sizeof(arr) / sizeof(arr[0]);
    int ret[2] = { 0,0 };
    singleNonDuplicate(arr, number1, ret);
    for (i = 0;i < number1;i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    printf("%d ", *ret);
    printf("%d", *(ret +1));
    return 0;
}

Tags: C p2p

Posted by andymoo on Mon, 02 May 2022 22:29:16 +0300