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))
Answer of the second one:
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner scn=new Scanner(System.in);
String x=scn.next();//L.H.S of the equation
int y=scn.nextInt();//R.H.S of the equation
int res=min(x,y);
if(res>=10000)
{
System.out.println(-1);
}
else
{
System.out.println(res);
}
}
For 1st problem, you can find max length subarray possible with sum as (totalSumOfArrayElements - X), then if found such subarray then answer will be (lengthOfArray - maxLenSatisfying).
Using 2 pointer algo you can find max length subarray satisying condition in O(n) time complexity.
def permute(s):
result = [[s]]
for i in range(1, len(s)):
first = [s[:i]]
rest = s[i:]
for p in permute(rest):
result.append(first + p)
return [[int(j) for j in i] for i in result]
def problem(s):
x,y=s.split("=")
data=permute(x)
newdata=[]
for i in range(1,len(x)+1,1):
for j in data:
if i==len(j):
newdata.append(j)
for i in newdata:
if sum(i)==int(y):
print(“str 1”,i)
return
print(“str -1”)
def check_constraint(s):
if (not (1<=len(s)<=10^3)):
print(-1)
elif (s.split("=")[0]==s.split("=")[1]):
print(1)
elif (not (len(s.split("=")[0])>=len(s.split("=")[1]))):
print(-1)
else:
problem(s)
A=input()
check_constraint(A)