How to Find a number which appears once and other numbers are twice ?

[Question]: In a given random array find a number which appears only single time
Example :
Random array input – [9,2,2,3,4,4,3] output = 9
Solution:
Step 1: Create a dictionary.
Step 2: Create loop and fill the keys with element occurrence.
Step 3: Create a loop and return the dictionary element which has only single occurrence .
T C : O(2n) S C : O(n)

// Question : Find the number that appears once, and the other numbers twice
T C : O(2n)   S C : O(n) 
func findNumberAppearOnce(arr: inout [Int]) -> Int {
    // setting up empty dictionary
    var hashObject: [Int:Int] = [:]
    // Fill the dictionary with elements occurrence count 
    for obj in arr {
        if hashObject[obj] == nil {
            hashObject[obj] = 1
        } else {
            hashObject[obj]!+=1
        }
    }
// Return the dictionary element which has only single occurrence 
    for (key, _) in hashObject where hashObject[key] == 1 {
      return key
    }
    return -1
}

var randomArray: [Int] = [9,2,2,3,4,4,3]
let uniqueAppearNumber = findNumberAppearOnce(arr: &randomArray)
print(" uniqueAppearNumber ", uniqueAppearNumber)// prints 9

Approach 2(Optimum) :- Using XOR operation
XOR operation gives value if 0 & value => value & 1^1 = 0

101
011
000
110
XOR Table
func findNumberAppearOnceUsingXOR(arr: inout [Int]) -> Int {
    var xorOutput = 0
    for obj in arr {
        xorOutput^=obj
    }
    return xorOutput
}

Leave a Comment

Your email address will not be published. Required fields are marked *