Question 1 (Minimum withdrawals - Solved, thanks to jan265):
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.
Constraints
1 <= N <= 10^5
1 <= ATM[i] <= 10^5
1 <= X <= 10^5
Question 2 (Minimum pluses):
Given an equation “x=y”, for example, “111=12”, you need to add pluses inside x to make the equation correct. In our example “111=12”, we can add one plus “11+1=12” and the equation becomes correct. You need to find the minimum number of pluses to add to x to make the equation correct. If there is no answer print -1.
Note that the value of y won’t exceed 5000. The numbers in the corrected equation may contain arbitrary amounts of leading zeros.
Input Format
The first line contains a string, A as described in the problem statement.
Constraints
1 <= len(A) <= 10^3
I have tried to do these problems with backtracking, but the test cases are too large. I can only pass half the cases. How can I do this? Any hint will be appreciated.
lhs,rhs=[i for i in A.split('=')]
rhs=int(rhs)
dp=[[10000 for i in range(rhs+1)] for i in range(len(lhs))]
dp[0][int(lhs[0])]=0 # For first digit in lhs
for i in range(1,len(lhs)):
num=int(lhs[0:i+1])
for j in range(rhs+1):
if num==j:
dp[i][j]=0
elif num>j:
minval=dp[i][j]
for k in range(i,0,-1):
rem=j-int(lhs[k:i+1])
if rem>=0 and dp[k-1][rem]+1<minval:
minval=dp[k-1][rem]+1
dp[i][j]=minval
if dp[len(lhs)-1][rhs]==10000:
return -1
else:
return dp[len(lhs)-1][rhs]
Am I doing this right? This code still cannot pass most of the test cases. (Time limit error)
For question 2, can you think of any test case…where there are different numbers of plus sign is required?
As they say minimum, like what is the significance of minimum?
(not a suggestion, just a thought, even i am not able to solve)
public static void equations (String pre ,String s1){
for (int i =1 ; i<s1.length();i++){
String head = s1.substring(0,i);
String body = s1.substring(i);
hs.add(pre+head+"+"+body);
pre = pre+head+"+";
if (body.length()>1)
equations(pre,body);
pre = pre.substring(0,pre.length()-(i+1));
}
}
initially pre string will be null and after the execution of equation method it will
add all the possible equation to static variable and hence you can get your desired answer.
I am attaching the code for Minimum Withdrawals. It’s a simple memoization trick.
import sys
sys.setrecursionlimit(10000)
mem_dict = dict()
def minimumWithdrawal(ATM,X):
if X == 0:
return X
if len(ATM) == 0:
return -1
if sum(ATM) < X:
return -1
def use_recursion(arr, start, end, X):
if X == 0:
return 0
if X <0 or start > end:
return len(arr) + 1
res = mem_dict.get((start, end, X))
if res == None:
left, right = use_recursion(arr, start + 1, end, X - arr[start]), use_recursion(arr, start, end - 1, X - arr[end])
res = 1 + min(left, right)
mem_dict[(start, end, X)] = res
return res
res = use_recursion(ATM, 0, len(ATM) - 1, X)
return -1 if res > len(ATM) else res
def main():
N = int(raw_input())
ATM=[None]*N
for j in xrange(N):
ATM[j] = int(raw_input())
X = int(raw_input())
result = minimumWithdrawal(ATM,X);
print result
if __name__ == "__main__":
main()
Calling the recursion utility function with initial start and end pointers and only returning the result if it is less than the total length of the array, which by the way is the maximum number of withdrawals that can be. So, if the answer is greater than the length, it signifies that there is no solution.
12+3+4+5+67
4
4 pluses is my answer.
i don’t know why all except two test cases show Runtime error in my solution.
from itertools import combinations
def powerset(iterable):
for n in range(len(iterable)-1,-1,-1):
yield from combinations(iterable, n)
def minimum_pluses(A):
x,y = A.split("=")
#x = "12345"
#y = "60"
y = int(y)
if int(x) == y:
return 0
else:
s = list('+'.join(list(x)))
#print(s)
idList = list(range(1,len(s),2))
#print(idList)
for a in powerset(idList):
temp = s[:]
for i in a:
temp[i] = ""
#print(''.join(temp))
if eval(''.join(temp)) == y:
print(''.join(temp))
return len(idList) - len(a)
break
else:
return -1
A = "1234567=91"
print(minimum_pluses(A))
