How Do I Reduce The Time Complexity Of This Code Snippet In Python?

I have a compare function here which compares 2 4-digit numbers (non-repeating digits) and gives x (no. of digits in both n1 and n2 and in the same position), and y (no. of digits

Solution 1:

It looks like there is no possible way you can get x and y without accessing the whole list. Although you may sort the list with nlogn,

Solution 2:

Numpy give a better vectorized solution. So both loop is replace with a vectored solution as follows:

1. For x we directly compare each index value to other same index value and then use np.sum to count number which are same.
2. For y we just want value check in a array which can be done using np.in1d as a vectorized solution.

---

import numpy as np

def compare(n1, n2):
    s1, s2 = str(n1), str(n2)

    l1 = np.array(list(s1))
    l2 = np.array(list(s2))
    x = np.sum(l1 == l2)
    y = np.sum(np.in1d(l2, l1)) - x
    print(x, y)
    
compare(1023, 2024)

OUTPUT :

2 1

Solution 3:

@DeGo said you can't go better than o(n). However, you code can be improved since you are doing things that are absolutely not necessary. I would rewrite the code as

from collections import Counter

def compare(n1, n2):
    digits_at_same_position, digits_at_diff_position = 0, 0
    s1, s2 = str(n1), str(n2)
    l1 = list(map(lambda x, y: x == y, s1, s2))
    digits_at_same_position = sum(l1)
    l2 = list((Counter(s1) & Counter(s2)).elements())
    digits_at_diff_position = len(l2) - digits_at_same_position
    return digits_at_same_position, digits_at_diff_position

print(compare(1234, 2435))

The class of efficiency is the same. However, this code will be faster than yours.

Output:

>> (1, 2)