Problem Statement: There is a unique ATM in Wonderland. Imagine this ATM as an array of numbers. You can withdraw cash only from either ends of the array. Sarah wants to withdraw X amount of cash from the ATM. What are the minimum number of withdrawals Sarah would need to accumulate X amount of cash. If it is not possible for Sarah to withdraw X amount , return -1.
Input Format: The first line contains an integer N, denoting the number of elements in ATM.
Each line I of the N subsequent lines (Where 0 <= I <N) contains an integer describing the cash in ATM.
The next line contains an integer X, denoting the total amount to withdraw.
1 <= N <= 10^5
1 <= ATM[i] <= 10^5
1 <= X <=10^5
|Sample Input||Sample Output||Explanation|
|2 1 1 3||-1||The total amount of cash in the ATM is 2, hence Sarah cannot withdraw an amount of 3.|
Let’s understand the problem first: In this problem you have given a ATM as a array of numbers every element in the array is the amount of money that can be withdrawn at a particular time. A person can withdraw money from either of the both ends of the array. You can’t take any fractional amount and in this problem the main objective is to get the minimum no of withdrawals to withdraw a certain amount of money from the ATM now understand it with a example.
Suppose the array is [1, 1, 1, 1, 1, 3, 2, 2]. And we want to withdraw 5 . we can withdraw from any side of end. Let’s attempt it from the end side after withdrawing 3 times we get amount of 7. But we can’t get 5. Important thing we can not take 1 from 3 to make it 5. So by attempting from end side we can’t get 5. Now lets try it from start end. After withdrawing 5 times we get 5.
But there is another way to make 5. We can withdraw amount 4 from end side and amount 1 from beginning of the array to make total amount of 5 . 5=2+2+1.
But in this way we need only 3 withdrawals to make it 5. So minimum withdrawals needed is 3.
Tricks to solve the problem: First try to make the desired amount from one side of the array. Then check whether amount can be withdrawal from that side and if possible then store the no of withdrawals required.
Then start adding from the other side removing one by one elements from the firstly chosen side. Means we will remove elements from the first side and start adding elements from the other side until all the elements of the beginning side is removed in this process continue checking the no of withdrawals and compare with the minimum value of withdrawals. It will be more clear if you observe the code.
Before moving to the solution we recommend you to attempt the problem first from yourself then move to the solution part.
Here, is our solution to the answer in Python.
# HackWithInfy Sample Paper Round-1 # Q. Minimum Withdrawals # All rights reserved www.codewindow.in a=int(input()) b= for i in range(a): temp=int(input()) b.append(temp) c=int(input()) if(sum(b)<c): print(-1) exit(0) d=b[::-1] sum1=0 i=0 j=0 minv=99999 while(i<len(b) and sum1<=c): sum1=sum1+b[i] i=i+1 i=i-1 r=i+1 flag=0 if(sum1==c and r<minv): flag=1 minv=r while(1): if(j<len(b) and sum1+d[j]<=c): sum1=sum1+d[j] j=j+1 r=r+1 elif(i>=0): sum1=sum1-b[i] i=i-1 r=r-1 else: break if(sum1==c and r<minv): minv=r if(sum1==c and r<minv): minv=r if(minv==99999): print(-1) else: print(minv)
Let’s Understand the code line by line:
First of all we have taken all the inputs in a, b, c. b is the list containing all the ATM amounts. Then I have checked if the amount is possible to withdraw from the ATM or not. If not possible then exit from code by printing -1 as output.
List d is the same as b but in reverse order to do the code easily. Sum1 is the amount that will be withdrawal so initialized it to 0. And for i and j also and minv is the minimum withdrawals possible so we assign it with a very high value.
Then in sum1 variable we started to make the sum of amounts from beginning of the list and i is denoting the last indexed number added in the sum1. In r we have stored the no of withdrawals taken to perform it from the beginning of the array.
Then we have checked if sum1 is equals to the desired amount or not .If sum1 is the desired amount we want to withdraw then we update the r value to minv.
After that we have started a infinite loop. Inside the loop we started adding numbers from the list d which is the reverse of b that means we are adding elements from the end of the list b. So we are checking if sum1 is less than c or not if less than c then we add d[j]. If sum1 is greater than c then we are removing the lastly added element from the beginning side of the list and so value of both i and r reduces and in the other case if we add elements from the d list then r value is again increasing and j is for denoting the last index of element added to sum1 from the list d.
The exit condition of the while loop is that when there sum1 will be greater than c and also there will be no elements present from the beginning of the array means the sum1 will contain only the sums from end side of the array.
Inside the while loop we have also checked if the value of sum1 is equals to the value of c or not in every iteration and if it is equal then we have updated the value of minv.
After the end of while loop we have checked for a final check to update the value of minv.
Lastly, if value of minv remains unchanged as it was initialized then it is not possible to withdraw the exact amount so output will be -1. Otherwise the output will be the value of minv.
Proof of successfully executing the code:
- Juspay Hiring Challenge | Think big with Functional Programming | Codewindow.in
- Exam Answers
- IBM Off Campus Hiring | Associate System Engineer | Codewindow.in
- FindMax Problem
- Walmart Off Campus Hiring | Walmart CodeHers | Codewindow.in
- Quadratic Equation Solution | Codewindow.in
- Accenture Solution | Code in Marathon | Codewindow.in
- Amazon Off Campus Internship Drive | Amazon WoW for the batch of 2022, 2023, and 2024 | Codewindow.in
- Binary Tree Combination
- Sum of all the prime divisors of a number
- Mindtree Interview Questions and Experience Part 1 | Codewindow.in
- Apisero Off Campus Recruitment Drive | Software Engineer | 2021 2020 2019 2018 | Codewindow.in
- Infosys Mega Off Campus HIring | Technincal Process Executive | Codewindow.in
- Amazon Off Campus Hiring | Software Development Engineer | 2021/2020/2019/2018 | Codewindow.in
- Question 3 Solution | Duplicate Elements Solution | Codewindow.in
- Question 2 Solution | Second Largest Solution | Codewindow.in
- Question 1 Solution | Palindrome Solution | Codewindow.in
- Question 2 Coding Solution | Weak String Problem | Codewindow.in
- Question 1 Coding Solution | Permutation Problem | Codewindow.in
- XL Dynamics Off Campus Hiring | 2022 2021 2020 | Codewindow.in
- Accenture Full Question Paper Set | Codewindow.in
- Accenture Aptitude Questions and Solution | Codewindow.in
- Accenture Logical Reasoning Questions and Solution | Codewindow.in
- MountBlue Solution | PlayGame Code | Codewindow.in
- MountBlue Solution | !On Off Code | Codewindow.in
- Revature Answer | 2021
- IBM Mixed Fraction Code Solution | CodeWindow.in
- IBM Volume of Pizza Slice Solution | CodeWindow.in
- Accenture Running Distance Code Solution
- Accenture Pizza Code Solution
- Cognizant GENC Off-Campus | 2021 | CodeWindow.in
- Revature Coding Solution with proof | Array Operation: Ascending order | Codewindow.in
- Coding Questions (76)
- HR Questions (4)
- Interview Experience (7)
- Job Info (134)
- Miscellaneous (43)
- Programming in C (56)
- Programming in C++ (6)
- Programming in JAVA (11)
- Programming in Python (126)
- Recruiting Companies (6)
- TCS NQT (23)
- Uncategorized (41)
- Wipro NLTH (8)
- WIpro NLTH Coding Solve (1)