Временная сложность двух алгоритмов для одной задачи

Question

Я пытался решить проблему на Hackerearth . Суть проблемы заключается в следующем:

Суссуту - всемирно известный маг. И недавно он был наделен властью удалять ТОЛЬКО ОДИН элемент из массива. Дан массив A (индекс начинается с 0) с N элементами. Теперь Суссуту МОЖЕТ удалить только тот элемент, который делает сумму ВСЕХ оставшихся элементов в точности делимой на 7. На протяжении всей своей жизни Суссуту был так занят магией c, что никогда не мог ладить с математикой. Ваша задача - помочь Суссуту найти первый индекс массива наименьшего элемента, который он МОЖЕТ удалить.

Ввод : первая строка содержит одно целое число N. Следующая строка содержит N пробела разделенные целые числа A _k , 0

Выходные данные : вывести одну строку, содержащую одно целое число, первый индекс массива наименьшего элемента, который он МОЖЕТ удалить и -1, если нет такого элемента, который он мог бы удалить!

Ограничения : 1 5

0 k <10 <sup>9

Вот алгоритм, который я пробовал, но он превышал ограничение по времени в некоторых тестовых случаях:

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)

Другой код, который работал нормально, приведен ниже:

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)))

Может кто-нибудь помочь мне понять, почему 1-й код превысил ограничение времени и почему 2-й код не ?? ??

Answer 1

В первом алгоритме сама сортировка равна O(n log n), поэтому сложность первого алгоритма l oop равна O(n)*O(n log n) = O(n² log n). Во втором случае вы просто l oop через входной массив три раза - так что его сложность O(n), намного ниже. Для очень больших входов первый тайм-аут, а второй - нет.

Answer 2

FWIW: вы можете избежать некоторой работы:

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]))

, которая выполняет работу за один проход. (Ваш код имеет один проход через A, «скрывающийся» в sum(A).)

Answer 3

Временная сложность первого алгоритма равна O(n^2 logn), поскольку вы сортируете массив в каждой итерации, а временная сложность второго составляет O(n).

Answer 4

Вам просто нужно удалить элементы, которые по модулю 7 совпадают с суммой списка:

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])

вывод:

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