CODEWITHSUNDEEP
pythonarrayspython-3.xalgorithmtime-complexity
Meghal Darji
Meghal Darji

Reputation: 75

Time complexity of two algorithms for same problem

I was trying to solve a problem on Hackerearth. The problem statement is as follows:

Sussutu is a world-renowned magician. And recently, he was blessed with the power to remove EXACTLY ONE element from an array. Given, an array A (index starting from 0) with N elements. Now, Sussutu CAN remove only that element which makes the sum of ALL the remaining elements exactly divisible by 7. Throughout his life, Sussutu was so busy with magic that he could never get along with maths. Your task is to help Sussutu find the first array index of the smallest element he CAN remove.

Input: The first line contains a single integer N. Next line contains N space separated integers Ak , 0 < k < N.

Output: Print a single line containing one integer, the first array index of the smallest element he CAN remove, and −1 if there is no such element that he can remove!

Constraints: 1 < N < 105

0 < Ak < 109

Here is the algorithm that I tried, but it exceeded the time limit on some test cases:

n = int(input())
A = list(map(int, input().split(' ')))
temp = sorted(A)

for i in range(n):
    temp[i] = 0
    s = sum(temp)
    temp = sorted(A)
    if s % 7 == 0:
        flag = True
        break
    flag = False

if flag == True:
    print(A.index(temp[i]))
else:
    print(-1)

Another code which worked fine is given below :

n = int(input())
A = list(map(int, input().split(' ')))
S = sum(A)
t = []
for a in A:
    if (S - a) % 7 == 0:
        t.append(a)
if len(t) == 0:
    print(-1)
else:
    print(A.index(min(t)))

Can anyone help me understand why the 1st code exceeded the time limit and why the 2nd code did not??

Upvotes: 0

Views: 617

Answers (4)

FernandoAMB
FernandoAMB

Reputation: 46

In the first algorithm, the sort itself is O(n log n), so the complexity of the first one's loop is O(n)*O(n log n) = O(n² log n). In the second one, you simply loop through the input array three times - so its complexity is O(n), far lower. For very large inputs, the first one will then timeout while the second one may not.

Upvotes: 2

Alain T.
Alain T.

Reputation: 42143

You simply need to remove an elements which has the same modulo 7 as the sum of the list:

import random

n = 10
A = [ random.randrange(n) for _ in range(n)]

modulo7 = sum(A)%7
index = next((i for i,a in enumerate(A) if a%7==modulo7),-1)

print(A,"sum:",sum(A))
if index < 0: 
    print("No eligible element to remove")
else:
    print("removing",A[index],"at index",index,"makes the sum",sum(A)-A[index])

output:

[4, 8, 4, 1, 8, 9, 6, 9, 4, 4] sum: 57
removing 8 at index 1 makes the sum 49

Upvotes: 1

Chris Hall
Chris Hall

Reputation: 1772

FWIW: you could avoid some work by:

V = [M]    * 7     # where max(A) < M
I = [None] * 7
s = 0
i = 0
for v in A:
    m  = v % 7
    s += m
    if v < V[m]: V[m] = v ; I[m] = i
    i += 1

s = s % 7

if I[s] == None:
    print("No answer!!!")
else:
    print("i=%d v=%d" % (I[s], V[s]))

which does the job in a single pass. (Your code has one pass across A "hiding" in the sum(A).)

Upvotes: 2

Ayoub Omari
Ayoub Omari

Reputation: 906

Time complexity of the first algorithm is O(n^2 logn) because you are sorting the array in each iteration, while time complexity of the second is O(n).

Upvotes: 2

Related Questions