Infosys | onsite | A lot of Sum

Anonymous User

130

Infosys Interview

Given :
N is array in range 1 to N lets save it as Arr
There are K Operations where Brr[i] = sum of array Arr(i)

I have explained more in Program itself

so I got the first 3 test cases correct but for bigger test cases failed because of time limit

is there any way we can make the code faster because the time limit exceeded

Here is my working solution which works but is having issues with bigger test cases

def solve(N,K):
    # this is the Operation we need to perform K times
    def Operation(Arr):
        sum  = 0;
		# New Array should be sum of pervious elements example [1, 2, 3, 4, 5] output [1, 3, 6, 10, 15] ie 1+2=3 , 1+2+3=6 and so on 
        newArr = list()
        for i in range(0,len(Arr)):
            sum = sum + Arr[i]
            newArr.append(sum)
        
        return newArr

	# This is our Initial Array from 0 to N
    Arr = list(range(1,N+1))

	# New Array which we will work on Operation
    Brr = Arr

	# Perform Operation K times as per requirement
    for i in range(0,K):
        Brr = Operation(Brr)

	# This should be the sum of last operation 
    return sum(Brr)

Sample Test Case 1 :

if solve(5,3)

solution :

126

Sample Test Case 2 :

if solve(1,3)

solution :

1

Error :

issue is for larger test cases its giving error if time limit exceeds 3 sec
Example Failed Test case:

start_time = time.time()
print(solve(5000,3000))
print("--- %s seconds ---" % (time.time() - start_time))

solution time :

3.9870870113372803 seconds

solution (very big):

131202569243861518177818039551235471149009664331828817643702806026264377943893107930530733678125994421413223270987311797038379027422172449187883094931929165736829744238670483079211257704073635630234444518704578227705907137102395242083163716234117263285940119732142835977682822894904928482456564626329285168980629081832510233156661436834553178535144980178639375735629998673181596522654677056438612580633804852936821148144437434743534860343183848028841918436195033884556299918268545975041185695782915179198191000662644650232215092502005785584632626917661671487485427067597242695500244035208583851548567282505951357978083899726287884709677801546074197957673607709811817774153765886848048283059292762026814812265116621345496067765884418606546154318224592302048249852654704341434034699057784501075617681732365855775185156008197046668982631935980949361283922641999016936126448090199085006729732384278006030808512270942254929088208965144143416413407306510475119629889337986123598656400899070461327251859779047822222115197785122275000273710398693154934513185214948147358358429681136915467236885826593287702430185749933443072883040618666814591841813155526199141192931134717137628289685348449194572250159109002045451367603467630231988591604738413650953482723334150817761163478465479329985018061230953982289999783082895920021922052754863957300719560415804710556143205190972553066930207122324794342339818955773625778676627479745091720218846707654067853164966554221698558404884043151790125501742453894895759899540501178641736147459174670746737227852697387246363757704848910217269274919422075506451378181591258783228244436611669156478334479642521258092183160392112470214972843107163835708107253089444091828768740110938205313037714558412036604540896194309536439073108204973445358398164543016825758661402699227067245647303638954529833620093010051339770608791239051632990591722940975048834188918146657810316404573259921901570452472934651211115345153098717386071384359792839134896879052874466988483791693019482659574305361032420393147528604275902589683671862058942885518433343076714352545136332293943361970042429954766747975706943594637903705090346216119354750229339274481735783751040344871548097247561348232399627811087444737566676326958302306730043581769338984378007468618909457569561590224336255646976543152800000

Comments (1)