CODEWITHSUNDEEP
c++arraysbitwise-operators
Darlyn
Darlyn

Reputation: 4938

Find the number that is present in array only once using bitwise operators

If we have an array , that contains numbers that occures there twice , and one number that occures only once ,we can use XOR operator to find it due it following communitative law. e.g

1 2 3 2 3 
1 ^ 2 ^ 3 ^ 2 ^ 3 = ( 2 ^ 2 ) ^ ( 3 ^ 3 ) ^ 1 = 1

But can we use bitwise tricks to find the number , that occures in array once when other numbers can occure n times , n > 1 ?

Upvotes: 0

Views: 389

Answers (2)

Andrey Turkin
Andrey Turkin

Reputation: 2509

There is a way to do so but not with binary operators. You can present each number as a vector of bits, and then sum all vectors together using sum (mod n). Resulting vector will represent that unique number.

For example, let's consider n=3 and sequence 2 3 5 2 5 5 2

Vectors are: [0 1 0], [0 1 1], [1 0 1], [0 1 0], [1 0 1], [1 0 1], [0 1 0]

Per-element sum of all the vectors is: [3 4 4]

Mod 3 that will be: [0 1 1] which amounts to 3 - unique element in the sequence.

This is a generalization of XOR trick; in fact XOR is exactly this operation - summation in mod 2.

Upvotes: 2

paxdiablo
paxdiablo

Reputation: 882116

With bitwise operators, no, not unless n is always even.

But there are plenty of other methods that can be used such as sort-and-scan for an item occurring once, or assigning each item to buckets if the input domain is limited somehow.

As an example of the first:

def findASingle(list):
    if list length is zero:
        return nothing
    if list length is one:
        return first item in list
    sort list
    for each item in last other than first and last:
        if item is different to both previous and next item:
            return item

And, for the second, assuming it's limited to (for example) single digit non-negative integers:

def findASingle(list):
    create count[0..9], all set to zero
    for each item in last:
        count[item] = count[item] + 1
    for each index 0 through 9 inclusive:
        if count[index] is 1:
            return index
    return nothing

Upvotes: 0

Related Questions