11
\$\begingroup\$

You are given an array of n+2 elements. All elements of the array are in range 1 to n. All elements occur once except two numbers, which occur twice. Your task is to find the two repeating numbers.

My solution is:

t=int(input()) #number of test cases
for _ in range(t):
    n=int(input()) # no. of array elements
    l=[int(x) for x in input().split()]  #array elements
    for i in range(1,n-1):
        if l.count(i)==2:  # using count function to count the elements
            print(i,end=' ')
    print()

How can I improve it? Currently, it shows time limit exceeded on hackerrank.

\$\endgroup\$
  • 1
    \$\begingroup\$ You have the challenge source? \$\endgroup\$ – Ludisposed Jul 25 '18 at 14:51
  • 2
    \$\begingroup\$ Does it even require nested loops? The condition of having almost all elements different can make solution O(n). After calculating a sum of all elements we basically know the sum of numbers which are repeated. Maybe we can do some other operation (multiplication? XOR?) to get a second equation and find repeated x and y as roots of that system of two equations? \$\endgroup\$ – Roman Susi Jul 25 '18 at 15:16
  • \$\begingroup\$ hackerrank.com/contests/smart-interviews/challenges/… is the problem source \$\endgroup\$ – SRK Jul 25 '18 at 17:01
  • 1
    \$\begingroup\$ That link goes to a 404 \$\endgroup\$ – Matt Ellen Jul 26 '18 at 11:20
11
\$\begingroup\$

You are given:

  • all the numbers are in the range 1 .. n
  • there are exactly 2 repeated numbers

You aren’t using either of these facts in your solution.

For the second, you could break out of the loop after printing the second number. This, by itself, might speed up the code enough to avoid the time limit.

But the true speed up comes from the first fact.

You can initialize a count array of n zeros. Each time you see a number, increment the count at that index. If you increase the count to 2, emit the number.

This avoids the l.count(i) function needing to loop through every element of the array. Done n times, this becomes an O(n²) operation. Maintaining a count array is O(n).


Note: due to 1-based numbers in challenge & 0-based lists in python, you’ll want to use a count array of n+1 zeros.


[ int(x) for x in input().split() ]

This line can take up a lot of time, and a lot of memory. Consider n=10000. The input will be split into a list of 10002 strings. Each of those strings is then converted to an integer, and stored in another list. Then the processing of the real algorithm begins.

But what if the duplicate are found near the start of the list? Have we created 9000 strings, and converted 9000 strings to integers for nothing?

We can use re.finditer(r"\d+", line) to split the input line into strings, with an important difference. The value returned is a "generator"; it only does enough work to return the first value, and then stops until the next value is requested. We can take each returned string, and convert it to an integer ... when requested.

numbers = (int(term.group(0)) for term in re.finditer(r"\d+", line))

Again, this is a generator expression. It has done no work as of yet. The first matching characters have not been found.

We can create a find_repeats(n, numbers) function that takes in a list of numbers, and returns a generator for any repeated numbers it finds.

def find_repeats(n, numbers):
  count = bytearray(n+1)   # was: count = [0] * (n+1)

  for number in numbers:
    count[number] += 1
    if count[number] == 2:
      yield number

The function doesn't care if we pass it a list of numbers, or an iterable object, or a generator. It will fetch number, one at a time, increment a count, and if it finds the count increase to 2, it will pause the function and return the number. If we've given the function a generator as input, we now have 2 chained, paused generators.

Since we are only looking for 2 duplicate pairs, lets link one more generator into our chain:

repeats = itertools.islice(find_repeats(n, numbers), 2)

islice returns a slice of the sequence. In this case, we are asking for only the first two values of the sequence.

Again, we still haven't done any work. The first character of line has not been examined. It won't be until we asked for any values from the repeats generator expression. Let's asked for them all.

print(*repeats)

This starts our repeat generator engine in motion. The regex finds the first "word" of digits, it gets converted to an int, and gets counted into the count array. Then the regex finds the next word, it gets converted to an int, and counted. When the first count is incremented to 2, the value is yielded to the islice generator (which maintains its own internal count of values), and passes it on to be accumulated into the print statement arguments. Then the regex finds the next word, which gets converted to an int and counted, and so on. Eventually, the second count of 2 is reached, and that value is yield to the islice generator, which also passes it on into the print statement arguments. Then the islice generator says "enough, I've emitted my two values", and stops. The print statement prints out the two values. The generators are discarded, before completing any addition (and unnecessary) work.

Example:

n = 15
line = "1 2 3 4 5 6 10 9 8 7 6 10 11 12 13 14 15"
numbers = (int(term.group(0)) for term in re.finditer(r"\d+", line))

repeats = itertools.islice(find_repeats(n, numbers), 2)
print(*repeats)

When this prints "6 10", finditer has not processed "11 12 13 14 15" into words, nor have they been converted to integers, nor have they been counted. You can add a print statement into the find_repeats method to verify this. The numbers that were counted were never converted into the list of numbers [1, 2, 3, 4, 5, 6, 10, 9, 8, 7, 6, 10] either, because that too was unnecessary; the generators simply created and emitted the values one at a time -- no list was necessary.

\$\endgroup\$
  • \$\begingroup\$ Excellent lazy approach. I would avoid declaring count upfront though, instead I'd use a dict, a defaultdict(int), a Counter or even a set given the specifics here of counting only up to two. \$\endgroup\$ – Mathias Ettinger Jul 25 '18 at 18:34
  • \$\begingroup\$ @MathiasEttinger Since we have a complete set of values ranging from 1 to n, the List[int], allocated once in its entirety, is the fastest, most memory efficient structure. A dictionary is a waste of time; compare using a number as a key to look up an entry in a hash table -vs- direct indexing! A Counter internally uses a dictionary, & set also uses hashing to lookup existence of the element in a hash-table. If Python had a Java's BitSet, which has direct indexing of bits 1..n, it could be a good replacement set. Lacking that, I'll stand behind my preallocated List[int]. \$\endgroup\$ – AJNeufeld Jul 25 '18 at 18:49
  • 1
    \$\begingroup\$ yes, but given the whole lazy approach, I find it quite odd to preallocate the whole memory. Thinking of inputs like n=100000 and numbers starting with '4 4 8 8 ...' \$\endgroup\$ – Mathias Ettinger Jul 25 '18 at 18:53
  • \$\begingroup\$ @MathiasEttinger Fair point, well made. Still, if the second duplicate is found in the latter half of the sequence, the dict/Counter/set would have exceeded its capacity 12-15 times, which would require rebinning the contents of the hash table 12-15 times, plus 500000+ memory allocations for each hash table entry. I'm thinking the preallocation of one structure amortized against the permutations of the positions of the pairs could be a win. \$\endgroup\$ – AJNeufeld Jul 25 '18 at 19:02
  • 1
    \$\begingroup\$ yes, that should be more into the spirit of the generators. All in all, I'm not against allocating upfront; it's just that it isn't as nice as the rest of the approach. \$\endgroup\$ – Mathias Ettinger Jul 25 '18 at 20:17
11
\$\begingroup\$

Minor

  • Consider using the unittest module instead of using input to test
  • Use a if __name__ == "__main__" guard
  • Make it a function
  • Don't print but return variables

Timing improvements

l.count(i) == 2

It will search the entire list from the start.

Let's take a sample input (worst case) of [2, 3, 4, 5, 6, 7, 8, 1, 1, 2, 2], it will search the entire list 10 times!

This can be done in \$ O(n) \$ (worst case), because we know

All elements of the array are in range 1 to n

  1. You can create a list temp with length n filling it with None or 0
  2. For every number in the array, check if the value in temp[i] is empty (0 or None)
    • If it is empty put the value on that position
    • If the number is the same as the value of the temp list, we have seen it before

Revised Code

def find_repeating(lst):
    counts = [None] * len(lst)
    for i in lst:
        if counts[i] is None:
            counts[i] = i
        elif i == counts[i]:
            yield i

Note

This has the disadvantage of continuing to loop after the numbers are found, to avoid this you could add the elements to another array and return when the length of the array is 2.

It will not make the most "beautiful" code, but it will be faster than @Peilonrayz's answer for anything but worst case, since that requires to loop through the entire array.

def find_repeating(lst, count=2):
    ret = []
    counts = [None] * len(lst)
    for i in lst:
        if counts[i] is None:
            counts[i] = i
        elif i == counts[i]:
            ret += [i]
            if len(ret) == count:
                return ret

Timing all solutions

enter image description here

\$\endgroup\$
  • \$\begingroup\$ Note: you want temp to have at least n+1 zeros due to the 1-based nature of the problem and 0-based nature of python list indexing. Fortunately len(lst) is n+2, and happens to exceed the requirement, but it would be wise to at least comment this bit of magic. \$\endgroup\$ – AJNeufeld Jul 25 '18 at 15:35
  • 2
    \$\begingroup\$ +1 except that temp is a terrible name; call it counts instead and initialise it to 0 (i.e. make it an integer list that keeps count of how often its index was seen). \$\endgroup\$ – Konrad Rudolph Jul 25 '18 at 15:59
  • \$\begingroup\$ Nice work benchmarking those solutions. What unit is the N-axis in? Thousands? Ten thousands? Millions? \$\endgroup\$ – AJNeufeld Jul 26 '18 at 13:44
  • \$\begingroup\$ @AJNeufeld 10 ** N So from range from 10 till 1 million \$\endgroup\$ – Ludisposed Jul 26 '18 at 13:47
  • \$\begingroup\$ Ah! Log-linear plot. Makes more sense now. Off by one error? I see 5 points: 10 100 1000 10,000 100,000? Or is it starting at 100 and going to 1 million? \$\endgroup\$ – AJNeufeld Jul 26 '18 at 13:56
9
\$\begingroup\$

l.count(i) will look at every element in l, so it is O(n). We're doing this for each element we see, making the entire loop O(n²).

A more efficient solution will use extra storage to reduce that complexity. I recommend storing each x into a set. If it's already in the set, then it's a duplicate, so print it, else add it to the set and print nothing.

\$\endgroup\$
  • 5
    \$\begingroup\$ Adding elements to a set, one at a time, causing the set to repeated grow, possibly rebinning multiple times, can be a speed bottleneck. Preallocating a list of integers to count the occurrences of each number requires one allocation and no binning, and should be faster. It also extends to finding numbers that repeat thrice, which a set can’t do. \$\endgroup\$ – AJNeufeld Jul 25 '18 at 15:41
7
\$\begingroup\$

You should make a function. First get the input like you are doing, but then call the function and display the output. This is good practice to get into, as then each part of your program is doing one thing.

def challenge(n, l):
    for i in range(1,n-1):
        if l.count(i)==2:  # using count function to count the elements
            yield i


t=int(input())
for _ in range(t):
    n=int(input())
    l=[int(x) for x in input().split()]
    print(*challenge(n, l))

After this you can just use collections.Counter to get the most_common:

def challenge(_, l):
    common = Counter(l).most_common(2)
    return (i for i, _ in common)

You can also make your input more Pythonic by:

  • Put spaces on either side of =.
  • Use better variable names. l -> numbers.
  • You only need to discard n in Python.
  • l doesn't have to be integers.
  • Use the if __name__ == '__main__': guard
import collections


def challenge(numbers, top=2):
    common = collections.Counter(numbers).most_common(top)
    return (i for i, _ in common)


if __name__ == '__main__':
    tests = int(input())
    for _ in range(tests):
        input()
        numbers = input().split()
        print(*challenge(numbers))
\$\endgroup\$
7
\$\begingroup\$

A sum of \$n\$ initial natural numbers is $$1+2+\cdots+n = \frac{n(n+1)}2$$ and a sum of their squares: $$1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}6$$ So these are the expected values of sums for \$n\$–item array without duplicates.

Now, if there are two duplicates \$x\$ and \$y\$, the respective sums of values and their squares will become $$\begin{cases}\sum v = n(n+1)/2 +x + y \\ \sum v^2 = n(n+1)(2n+1)/6 + x^2 + y^2\end{cases}$$

If you find \$y\$ as a function of \$x\$ from the first equation: $$y=\sum v - n(n+1)/2 - x$$ and plug it into the second one, you'll obtain a quadratic equation with single unknown \$x\$.

So you can just scan the whole array, summing values and their squares, then solve a quadratic equation to obtain \$x\$ and then \$y\$.

\$\endgroup\$
  • \$\begingroup\$ +1, scrolled way too far to find this. This is optimal in both runtime and memory usage. This should be the answer \$\endgroup\$ – user2023861 Jul 26 '18 at 13:59
  • \$\begingroup\$ @user2023861 THX. This might become the answer at Stack Overflow as a valid algorithmic hint. But this is certainly not a code review, so it won't gain much appreciation here. :) \$\endgroup\$ – CiaPan Jul 27 '18 at 20:34
  • \$\begingroup\$ what about this request from the OP? How can I improve it? Currently, it shows time limit exceeded on hackerrank \$\endgroup\$ – user2023861 Jul 30 '18 at 12:56
  • \$\begingroup\$ @user2023861 IMHO you can't improve it substantially. But you can replace the algorithm with a faster one. And a possible faster one follows from my answer. What else should I write, the whole new implementation? \$\endgroup\$ – CiaPan Jul 30 '18 at 14:06
5
\$\begingroup\$

Another approach is to sort your list what is O(n log n) complexity and then compare only two adjacent elements which is O(n). Combined O(n log n). If there are duplicate they will be next to each other in a sorted list. Just pass a list with number to this function and it will give you a list with numbers that are duplicate. Or an empty list if there are no duplicate.

#nums is a list with numbers

def find_duplicate(nums):
    dublicates = []
    nums.sort()
    for i in range(len(nums)-1):
       if nums[i] == nums[i+1]:
          dublicates.append(nums[i])
    return dublicates
\$\endgroup\$
  • \$\begingroup\$ Sry, typo... Fixed \$\endgroup\$ – Predicate Jul 25 '18 at 15:33
  • \$\begingroup\$ Also, it is "duplicates", not "dublicates" and currently your indentation is a bit messed up. \$\endgroup\$ – Graipher Jul 25 '18 at 16:38
  • \$\begingroup\$ sry, commes from russian.) There it is with a "b" \$\endgroup\$ – Predicate Jul 25 '18 at 16:49
  • 2
    \$\begingroup\$ @MattEllen or use the pairwise recipe \$\endgroup\$ – Mathias Ettinger Jul 27 '18 at 14:10
  • 1
    \$\begingroup\$ @S.G. having tested both of our methods, yours is faster. However, you should probably break out of the loop once you get 2 hits. \$\endgroup\$ – Matt Ellen Jul 29 '18 at 7:46
4
\$\begingroup\$

Using CiaPan's answer, combined with some numpy, we can design quite an efficient solution. It does have some overhead which makes it slower for small lists, but for lists with more than 100 elements it is about as fast as Ludisposed's answer, and for larger arrays it is blazingly fast:

import time
import numpy as np

def find_repeating(lst, count=2):
    ret = []
    counts = [None] * len(lst)
    for i in lst:
        if counts[i] is None:
            counts[i] = i
        elif i == counts[i]:
            ret += [i]
            if len(ret) == count:
                return ret

def find_repeating_fast(lst):
    n = len(lst)-2
    num_sum = -n*(n+1)//2 + np.sum(lst)
    sq_sum = -n*(n+1)*(2*n+1)//6 + np.dot(lst, lst)

    root = (sq_sum/2 - num_sum*num_sum/4)**.5
    base = num_sum / 2
    a = int(base - root)
    b = int(base + root)
    return a, b


tests = int(input())
print("Comparison to Ludisposed's solution (worst case):")

for k in range(tests):
    inp = input()
    iterations = 10
    t0 = time.clock()
    for _ in range(iterations):
        test = [int(i) for i in inp.split()]
        find_repeating(test)

    t1 = time.clock()

    for _ in range(iterations):
        test_np = np.fromstring(inp, dtype=np.int64, sep=' ')
        find_repeating_fast(test_np)

    t2 = time.clock()
    print("Time per iteration (10^%d): %9.2fµs /%9.2fµs, speedup: %5.2f" % (
        k+1, 
        (t1-t0)/iterations*1e6,
        (t2-t1)/iterations*1e6, 
        (t1-t0)/(t2-t1))
    )

To ensure that both functions are timed properly, I give the same string to each of them, which is read from input(). The test file looks like this:

6
1 2 3 4 5 6 7 8 9 10 1 9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 99
[4 more lines of increasing size...]

Note that I used the worst case array for testing, with the repeating elements on the very end. Here are the results from my machine:

Comparison to Ludisposed's solution (worst case):
Time per iteration (10^1):      5.60µs /    16.10µs, speedup:  0.35
Time per iteration (10^2):     32.80µs /    14.60µs, speedup:  2.25
Time per iteration (10^3):    291.60µs /    43.40µs, speedup:  6.72
Time per iteration (10^4):   3043.70µs /   403.80µs, speedup:  7.54
Time per iteration (10^5):  32288.70µs /  3353.60µs, speedup:  9.63
Time per iteration (10^6): 329928.50µs / 32224.60µs, speedup: 10.24

Here we can clearly see the overhead of using numpy, but that the improvement is significant for large arrays. It should also be noted that this method fails with an integer overflow for arrays larger than \$ \sim 10^7\$. This can be rectified using dtype=object when creating the numpy array, but then the speedup is significantly reduced.

It should also be noted that this solution is also faster for the best case, even if the difference is slightly smaller:

Comparison to Ludisposed's solution (best case):
Time per iteration (10^1):     15.10µs /    41.60µs, speedup:  0.36
Time per iteration (10^2):     54.20µs /    28.90µs, speedup:  1.88
Time per iteration (10^3):    476.10µs /    87.50µs, speedup:  5.44
Time per iteration (10^4):   3204.40µs /   371.10µs, speedup:  8.63
Time per iteration (10^5):  27249.40µs /  3304.90µs, speedup:  8.25
Time per iteration (10^6): 269125.60µs / 32336.10µs, speedup:  8.32
\$\endgroup\$
  • \$\begingroup\$ You’re cheating! You aren’t including the time to convert the list to a numpy array. You should move test_np = np.array(test) to just before find_repeating_fast(test_np) (inside the iterations loop). I’m certain you’ll still see improvements, just not as large. \$\endgroup\$ – AJNeufeld Jul 27 '18 at 13:52
  • \$\begingroup\$ I was conflicted about how it should be timed, since both solutions are heavily bound by I/O. I have updated my code, will post the new version. \$\endgroup\$ – maxb Jul 27 '18 at 14:26
  • 1
    \$\begingroup\$ @AJNeufeld it was actually a bit difficult to create the numpy array quickly while making the tests fair. I considered using numpy.fromfile, but since that reads binary files it too seemed like cheating. When I used numpy.array(test) my code was not faster, but then I found numpy.fromstring and it saved my solution. \$\endgroup\$ – maxb Jul 27 '18 at 14:39
2
\$\begingroup\$

Use collections.Counter if you can, it's the right way to go. It's linear time to construct and effectively linear time to find the 2 elements which apear twice

from collections import Counter

def two_repeated_elements(x):
    return [n for n, count in Counter(x).most_common(2)]

two_repeated_elements([1, 2, 3, 4, 1, 2])  # [1, 2]
\$\endgroup\$
-2
\$\begingroup\$

Your approach: Count iterates throuh the whole array for every element. That mean n^2 times. Better solution: Do not compare numbers that were already compared. You should compare a number only with numbers infront of it.

#list with your numbers 
num_list = [...]

for i in range(len(num_list)):
    for j in range(i+1, len(num_list)):
        if num_list[i] == num_list[j]:
            print(num_list[i])
\$\endgroup\$
  • 4
    \$\begingroup\$ That still scales as O(n²) (but only half as much work as comparing every pair). \$\endgroup\$ – Toby Speight Jul 25 '18 at 15:12
  • \$\begingroup\$ It also only finds one pair; their are two pairs to find. \$\endgroup\$ – AJNeufeld Jul 25 '18 at 15:44
  • \$\begingroup\$ It is a very unclear description then... fixed \$\endgroup\$ – Predicate Jul 25 '18 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.