CRNA1-Editorial (2021 HEADLINES)

PROBLEM LINK:

Contest

Author: Hareesh V

DIFFICULTY:

Simple

PREREQUISITES

Math

PROBLEM:

You are given a permutation of first n squares but one of the squares in the permutation is missing and one is repeating your task is to find the missing square

EXPLANATION:

This problem can be easily solved by using the sum of the first n squares formula.
sum of first N square = n(n+1)(2n+1)/6
Now let’s store this value as the original sum and find the sum of the n numbers given let this be the given sum.if we subract the original sum from the given sum everythings cancels out except the missing square and repeated square so from this we find the difference between the missing square and repeated square let this be dif.now we search the given sequence of numbers to find the number which is occurs twice and subtract dif from this number and the result will be the missing square

TIME COMPLEXITY

Time complexity is O(n)

SOLUTIONS:

Setter's Solution
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,f.readline().split()))
    d={}
    for i in a:
        if(i not in d):
            d[i]=1
        else:
            rep=i
    asum= n*(n+1)*(2*n+1)//6
    tsum=sum(a)
    print(asum-tsum+rep)

Feel free to share your approach, if you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

1 Like