PROBLEM LINK:
Author: Kapil Bansal
Tester: Sankalp
DIFFICULTY:
EASY
PREREQUISITES:
Math
PROBLEM:
There is an array of size N.
- Choose two subsequent indices whose values have odd number of divisors.
- Find the indices which have maximum sum(inclusive)
EXPLANATION:
Every perfect square has odd number of divisors.
Therefore, first we need to find two consecutive numbers which are perfect squares.
Then we will need to find the pair which will give us the maximum cards.
SOLUTIONS:
Setter's Solution
def getMaxCard(n,c):
ec = []
for i in range(n):
# To ensure the number is a perfect square
if c[i]**0.5 == int(c[i]**0.5):
ec.append(i)
if len(ec) <= 1:
return 0
maxCard = ec[1] - ec[0] + 1
for i in range(1,len(ec)-1):
if maxCard < ec[i+1] - ec[i] + 1:
maxCard = ec[i+1] - ec[i] + 1
return maxCard
for _ in range(int(input())):
n = int(input())
c = list(map(int,input().split()))
print(getMaxCard(n,c))
Feel free to share your approach. Suggestions are always welcomed