GreekforGreeks Problem solving | Subarray with given sum | Google interview question for python with solution

Google interviews problems solution and Problem

Problem Statement:

Given an unsorted array B of size N of non-negative integers, find a continuous sub-array which adds to a given number S.

Explanation of the problem statements

So, our 1st step is complete that's, understands the coding problem.

Format to take the input

The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. The first line of each test case is N and S, where N is the size of the array and S is the sum. The second line of each test case contains N space-separated integers denoting the unsorted array elements.

Format of the output

For each test case, in a new line, print the starting and ending positions(1 indexing) of the first such occurring subarray from the left if sum equals to subarray, else print -1.

Constraints:

1 <= T <= 100

1 <= N <= 107

1 <= Ai <= 1010

Understand the format of the output

Example:

Input:

2                                <== Number of the Test cases

5 12                           <== Number of the element N and Sum S

1 2 3 7 5                    <== Element of the array

10 15                         <== Second test case of number of the element N and Sum S

1 2 3 4 5 6 7 8 9 10   <== Element of the array

Output:

2 4            <== Output of the first test cases

1 5            <== Output of the second test cases

Explanation of the output:

Testcase1: the sum of elements from 2nd position to 4th position is 12

Testcase2: the sum of elements from 1st position to 5th position is 15

How to solve the problem using my personal method

Steps of the program:

• First, we will take the number of test cases.
• Then we will run the while loop according to the test cases.
• Then we will take the length of the list and sums that we want to output.
• Then we will separate the length(size) and Sum.
• Then we will take the list from the user.
• Then we will check the subarray and check is equal to the given sum or not.
• If they equal to the given sums then we will print the location of the subarray.
• And if it is not equal to this or greater than the given sum we will start the sums of the subarray from the 2 elements.
• After when the one test cases will close then we will minus the 1 number from the test cases.
• 
  

The solution in Python3:(code)

# Python program to sum the continuous subarray is equal to the given sum.

# First we will take the number of the test cases.
T=int(input("Enter the Number of Testcases"))



# Then we will run the while loop according to the test cases.

while(T>0):

    

    # Then we will take the length of the list and sum that we want output. 

    NS=[int(x) for x in input("First Enter the Size of the list and sum of the Number").strip().split()]

    

    # Then we will separate the length(size) and Sum.

    n=NS[0]

    k=NS[1]

    

    # Then we will take the list from the user.

    list=[int(x) for x in input("Enter the list").strip().split()]

    last,start,start_sum,flag = 0, 0, 0, False

    

    # Then we will check the subarray and check is equal to the given sum or not. 

    for i in range(n):

        start_sum += list[i]

        if(start_sum>=k):

            last = i

            while(k<start_sum and start<last):

                start_sum -= list[start]

                start = start+1

            if(start_sum==k):

                print(str(start+1) + " " + str(last+1))

                flag=True

                break

    if flag==False:

        print(-1)

    

    # After when the one test cases will close then we will minus the 1 number from the test cases.

    T=T-1

# This code is contributed by the Ankur Patel.