CODEWITHSUNDEEP
pythonpython-3.xalgorithmoptimization
Aman Seth
Aman Seth

Reputation: 29

Sum of a large list in python

Calculate the index of an integer from a given large list whose removal does not effect the mean of the list

I have tried linear time approach but it seems to fail test cases having numbers above 10^9 and the size of the list exceeds 10^5. Please suggest some better approach to solve this problem if any or to suggest more efficient way to sum large list with large values . Here is my code below :

for _ in range(int(input())):
    n=int(input())
    #ar=list(map(int,input().split()))
    ar=[int(x) for x in input().split()]
    me=sum(ar)/n
    for j in range(n):
        #arr2=deepcopy(ar)
        arr2=ar[:]
        #arr2=[]
        #for _ in ar:
         #   arr2.append(_)
        arr2.remove(ar[j])
        if (sum(arr2)/(n-1))==me:
            print(j+1)
            break
    else:
        print("Impossible")

The code fails in two of the 10 test cases just because of increase in the len of the list and size of the integer

Upvotes: 0

Views: 1264

Answers (2)

Alain T.
Alain T.

Reputation: 42133

This looks more like a math problem than an algorithm challenge:

given that mean = sum(list)/len(list), we need a value k such that:

mean = (sum(list)-k)/(len(list)-1)

Which a little algebra tells us is:

k = sum(list) - mean * (len(list)-1)

k = sum(list) - mean * len(list) + mean

k = sum(list) - sum(list) + mean     <-- because mean*len(list) = sum(list)

k = mean

for example:

a  = [1,2,3,4,5,6,7]
k  = sum(a)/len(a) # 4
ik = a.index(k)    # 3

Upvotes: 0

Yida Lin
Yida Lin

Reputation: 187

You seem to make a deep copy of the entire array in each iteration, which is expensive. Why not just check whether an item equals the mean?

for _ in range(int(input())):
    n = int(input())
    ar = [int(x) for x in input().split()]
    mean = sum(ar) / n
    found = False

    for j in range(n):
        if ar[j] == mean:
            print(j, " is the result.")
            found = True
            break

    if not found:
        print("Impossible")

Upvotes: 2

Related Questions