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

Google interviews problems solution and Problem

coding problem


In this post, we will discuss how to handle any coding problem and how to solve problems in just 4 Steps and also how to analyze the problem statements and how to understand the problem and make a solution step by step. If you understand the coding problem, then the problem becomes so easy.

So, our first step to understand the coding problem, and then we will divide the problem into steps, so, this can help us to solve problems in a short period of time.
Problem statements are given below.

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

The problem statements want to explain to us that, one unsorted array was given to us, and the named of the unsorted array is B. And array is non- negative integers. And they also give the size of the array named N. And they also give the one number that's S.

Now our task is to find the sum of the continuous sub-array which is equal to the S number. 

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

So, we need to print the starting and ending position of the continuous subarray from left to right and if the sum is not equal to the sum S then we need to print -1.


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

We, solve the problem in the 4 steps:

  1. Analyze the problem
  2. Take the input from the user
  3. Apply the logic to solve the problem
  4. Print the output


1. So, we need to analyze or understand the problem statement that we have done already above. 

2. Now our second step to take the input from the user and note that only in the input format that was given above. 
So, we first we take the input of the number of the test cases and we named the variable "T".
And in the second line, we want to take the list from the user for N and S and then split the list by using the for loop.
And in third, we take the unsorted array and split this array into the elements.
So, our second step is also completed.

3. The third step is to apply logic to get an exact answer.
So, first of all, we apply the while loop to take all the test case input from the users.
Then we will run the for loop to check the subarray is equal to the sum or not. 

4. if the subarray is equal to the sum then we find the position of the for loop and print it otherwise we print the -1.

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.


Input:

2

5 6

1 2 3 7 5

10 7

1 2 3 4 5 6 7 8 9 10


Output:

1 3

3 4

If you have a better solution or query, please share it in a comment or Email.

Next Post Previous Post
1 Comments
  • Cracking the coding interview
    Cracking the coding interview February 2, 2021 at 7:43 PM

    Interesting problem. Looking forward for more problems on algorithms, data structures as well as geeksforgeeks amazon interview questions for preparations of interviews.

Add Comment
comment url