[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
1 | 0 | 1 |
0 | 1 | 1 |
0 | 0 | 0 |
1 | 1 | 0 |
func findNumberAppearOnceUsingXOR(arr: inout [Int]) -> Int {
var xorOutput = 0
for obj in arr {
xorOutput^=obj
}
return xorOutput
}