Site background image

Codewars solution

Find unique number

  • author

    Sounak

  • tags

    • python
    • codewars

  • year

    2022

This is my solution for CodeWars problem for 6 kyu. In this task, an array of numbers is given which all numbers are equal except for one. The challenge is to find the unique number and return it.

Initial approach

The given problem infers that the array(in Python represented as list) will have only two kinds of numbers. The first one will be the unique number and the other one is the number that fills the rest of the array. To put it in simpler way, the type of arrays or lists this program will receive will be like : [ 1, 1, 1, 2, 1, 1 ] or [ 0, 0, 0.55, 0, 0 ].

Initially, it was tempting enough to come up with a brute-force solution that follows the following pseudo-code:

  1. Loop over the array
  2. Select the current item
  3. Check the number of times the current item is present in the list. I.e. if the current item is present 9 times in the array etc.
  4. If the current item is present exactly one time, return the current item and break from the loop.
  5. If the current item is not present exactly once, the loop should continue.

Even though this algorithm solves the problem, it is not that efficient. If the unique item is present at the end of the array, the loop will be executed for all the items prior to the unique item. This would mean, the time complexity of the algorithm will be of order O(n) where n is the number of items present in the array.

Better approach

Luckily in Python, there is a built-in data-structure called set( ). A set is an unordered collection with no duplicate elements. If I converted the list from the arguments to a set, I'll have to deal with only 2 elements.

def find_uniq(arr: list) -> int:
    # [1, 1, 1, 1, 1, 12, 1, 1, 1] gets reduced to {1, 2}. The set is again converted to list
    two_kinds = list(set(arr))

Scroll left-right

Now that we have only two items to check, we have reduced the looping count from n to 2 i.e. O(n) to O(1).

Now all I'm left to do is to get the two numbers' individual count. For that, we can use the Python count method available on the list types. After these two operations, I'll return the number which exists exactly once and that is the solution for the problem.

def find_uniq(arr: list):
    # get the two kinds of numbers from the list by converting to the set type
    a, b = set(arr)
    # arr has a method called count which returns the number of times a number is present in arr
    return a if arr.count(a) == 1 else b

Scroll left-right

Conclusion

This is my solution for find the unique number using Python. If you have a better solution, please let me know about the same. If you have any queries about the solution, feel free to ping me up on my social media links.

Check out all blogs