GreekforGreeks Problem solving | Subarray with given sum | Google interview question for python with solution
Google interviews problems solution and Problem
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.
1 <= T <= 100
1 <= N <= 107
1 <= Ai <= 1010
Understand the format of the output
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
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
- Analyze the problem
- Take the input from the user
- Apply the logic to solve the problem
- Print the output
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 k=NS # 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.
1 2 3 7 5
1 2 3 4 5 6 7 8 9 10
If you have a better solution or query, please share it in a comment or Email.
Interesting problem. Looking forward for more problems on algorithms, data structures as well as geeksforgeeks amazon interview questions for preparations of interviews.