DSC-IIITL / GitGrind

9 stars 58 forks source link

added alternate solution for longset_subarray #50

Closed Priyanshu-2005 closed 9 months ago

Priyanshu-2005 commented 9 months ago

solved the problem using better solution

issue no #36

Priyanshu-2005 commented 9 months ago

logic: traverse through the array and store prefix sum in map as key and position of iteration element as value count the length till when sum becomes equal to required sum

if sum-k is availaible in the map then count the length of array from the current position of iteration to key to the element which has value has key equal to the sum-k

explanation of code

firstly input size and elements of array then input the sum for which we want the longest subarray

define a function longest subarray ,pass array ,array length and sum to the function inside the function intialize the data structure map initialize a variable sum and rem to keep track of sum,maxlen traverse through the entire array using the loop and increment in each iteration by element of arrays also initialize each <key ,value>pair in map key=sum value =i

when the value of variable sum becomes equal to k then if the variable maxlen is smaller then modify the value of maxlen to the length of the array traversed

then initialize the variable rem in which we store the value of variable sum-sum required(k)

if rem is already there in map then initialize a varilble l to store the length of the subarray required then compare l to maxlen if maxlen is smaller then modify the variable maxlen to length of subarray l

then return maxlen so that we get output as maxlen

Priyanshu-2005 commented 9 months ago

@Illuminati9 @PavanaSakethaRam changes made (vscode files removed)