Can someone help me with these two Infosys HackWithInfy practice questions?

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.

2 Likes

First question
Find the largest subarray with sum = (Total sum - X) and then the answer becomes (array length - subarray length)

Second question
I believe it can be done with DP. I don’t know exactly, but I guess I have done a similar problem before on a different platform.

Hope this helps :slightly_smiling_face:

3 Likes

Thank you so much. The method for first question worked.

2nd problem :
One of the state could be dp[i][j] : minimum number of pluses required to form number j , considering first i characters.

Now think about how to make the transition. Best of luck!!!

Can you please give me link to these problems, and where can I test my solutions ?

1 Like

https://infytq.onwingspan.com/en/viewer/iap/lex_auth_0132317475110666243

  1. Register
  2. Then sign in
  3. Then click on HackWithInfy Sample Paper - Round 1
1 Like

def minimum_pluses(A):

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)

thanks brother.

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)

1234567=91

There are ways to split the number with 5 pluses or 4 pluses.

Please help me out if you can solve it.

QUESTION 2 (MIN PLUSES>

static HashSet hs = new HashSet<>();

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.

1 Like

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()
1 Like

Additionally, here is the code for Beautiful Function.

def beautifulFunction(N):
    __sum = 0
    while(N > 9):
        last_digit = N % 10
        __sum += 10 - last_digit
        N //= 10
        N += 1
        while(N % 10 == 0):
            N //= 10
            
    return __sum + 9

def main():

    N = int(raw_input())
    result = beautifulFunction(N);
    print(result)
if __name__ == "__main__":
    main()

Here’s my take on Minimum Pluses, however it’s facing TLE.

import sys
sys.setrecursionlimit(10000)

memo_dict = dict()
sum_dict = dict()
def minimum_pluses(A):
    def __add(__str):
        __sum = sum_dict.get(__str)
        if __sum == None:
            __new_str = list(map(int, __str.split("+")))
            __sum = sum(__new_str)
            sum_dict[__str] = __sum
        return __sum
    
    def get_val(__str):
        res = __str.split("=")
        return res[0], int(res[1])
    
    def use_recursion(__str, idx, val):
        if __add(__str) == val:
            return 0
        if idx >= len(__str) - 1:
            return 999999
        
        res = memo_dict.get((__str))
        if res == None:
            left = 1 + use_recursion(__str[:idx + 1] + "+" + __str[idx + 1:], idx + 2, val)
            right = use_recursion(__str, idx + 1, val)
            res = min(left, right)
            memo_dict[(__str)] = res
        return res
        
    tup = get_val(A)
    res = use_recursion(tup[0], 0, tup[1])
    return -1 if res >= 999999 else res
    
def main():

    A = raw_input()
    result = minimum_pluses(A);
    print result
if __name__ == "__main__":
    main()

res = use_recursion(ATM, 0, len(ATM) - 1, X)
return -1 if res > len(ATM) else resstrong text

What is the use of this lines?

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))

I have attached the recursive solution for Minimum Pluses…
// Author - Soumak Poddar ™
#pragma GCC optimize(“Ofast”)
#pragma GCC target(“avx,avx2,fma”)

    #include<bits/stdc++.h>
    using namespace std;

    #define ll long long int
    #define sll signed long long int
    #define ull unsigned long long int
    #define umax uintmax_t

    #define um unordered_map
    #define us unordered_set
    #define mm multimap
    #define pq priority_queue
    #define pi pair<int,int>
    #define vi vector<int>
    #define vll vector<ll>
    #define gi greater<int>

    #define mp make_pair
    #define pb push_back
    #define fir first
    #define sec second
    #define M 1000000007

    template<typename T>
    T gcd(T a,T b)
    {
       if(a==0)
          return b;
       return gcd(b%a,a);
    }
    template<typename T>
    T lcm(T a,T b)
    {
       T g=gcd<T>(a,b);
       return (a*b)/g;
    }
    template<typename T>
    bool isprime(T n)
    {
       if(n<=1)
          return false;
       for(int i=2;i<sqrt(n);i++)
          if(n%i==0)
             return false;
       return true;
    }
    vector<bool> prime;
    void seive(ll n=4000000)
    {
       prime.resize(n+1);
       fill(prime.begin(),prime.end(),true);
       prime[0]=prime[1]=false;
       for(ll i=2;i*i<=n;i++)
       {
          if(prime[i]==true)
          {
             for(ll j=i*i;j<=n;j+=i)
                prime[j]=false;
          }
       }
    }
    // const ll s=1000000;
    // vector<ll> pr;
    // ll lp[s+1];
    // void modified_sieve()
    // {
    //    for(int i=2;i<=s;i++)
    //    {
    //       if(lp[i]==0)
    //       {
    //          lp[i]=i;
    //          pr.pb(i);
    //       }
          
    //       for(int j=0;j<(ll)pr.size() && pr[j]<=lp[i] && i*pr[j]<=s;++j)
    //       {
    //          lp[i*pr[j]]=pr[j];
    //       }
    //    }
    // }

    void solve();
    int main()
    {
       ios_base::sync_with_stdio(false);
       cin.tie(NULL);
       cout.tie(NULL);

       #ifndef ONLINE_JUDGE
          freopen("input.txt", "r", stdin);
          freopen("error.txt", "w", stderr);
          freopen("output.txt", "w", stdout);
       #endif
       
       ll t=1;
       // cin>>t;
       while(t--)
       {
          solve();
          // cout<<"\n";
       }

       cerr<<"Time Taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
       return 0;
    }

    void soln(string s,int sum,int tmp,int plus,int &ans)
    {
       if(s=="")
       {
          if(tmp==sum)
          {
             ans=min(ans,plus-1);
          }

          return;
       }

       for(int i=1;i<=s.length();i++)
       {
          string lp=s.substr(0,i);
          string rp=s.substr(i);
          int lps=stoi(lp);

          soln(rp,sum,tmp+lps,plus+1,ans);
       }
    }

    void solve()
    {
       string s;
       cin>>s;
       int n=s.length();
       string num="",ans="";
       int i=0;

       while(i<n)
       {
          if(s[i]=='=')
             break;
          num+=s[i++];
       }
       i++;
       while(i<n)
       {
          ans+=s[i++];
       }

       int rnum=stoi(ans),a=INT_MAX;
       soln(num,rnum,0,0,a);

       if(a==INT_MAX)
          cout<<-1;
       else
          cout<<a;
    }

Can anyone help me in optimizing it…

Same for my code…
Check it below

Answer to the First Question:-

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#include<bits/stdc++.h>
using namespace std;

#define ll long long int
#define sll signed long long int
#define ull unsigned long long int
#define umax uintmax_t

#define um unordered_map
#define us unordered_set
#define mm multimap
#define pq priority_queue
#define pi pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define gi greater<int>

#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define M 1000000007

template<typename T>
T gcd(T a,T b)
{
   if(a==0)
      return b;
   return gcd(b%a,a);
}
template<typename T>
T lcm(T a,T b)
{
   T g=gcd<T>(a,b);
   return (a*b)/g;
}
template<typename T>
bool isprime(T n)
{
   if(n<=1)
      return false;
   for(int i=2;i<sqrt(n);i++)
      if(n%i==0)
         return false;
   return true;
}
vector<bool> prime;
void seive(ll n=4000000)
{
   prime.resize(n+1);
   fill(prime.begin(),prime.end(),true);
   prime[0]=prime[1]=false;
   for(ll i=2;i*i<=n;i++)
   {
      if(prime[i]==true)
      {
         for(ll j=i*i;j<=n;j+=i)
            prime[j]=false;
      }
   }
}
// const ll s=1000000;
// vector<ll> pr;
// ll lp[s+1];
// void modified_sieve()
// {
//    for(int i=2;i<=s;i++)
//    {
//       if(lp[i]==0)
//       {
//          lp[i]=i;
//          pr.pb(i);
//       }
      
//       for(int j=0;j<(ll)pr.size() && pr[j]<=lp[i] && i*pr[j]<=s;++j)
//       {
//          lp[i*pr[j]]=pr[j];
//       }
//    }
// }

void solve();
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);

   #ifndef ONLINE_JUDGE
      freopen("input.txt", "r", stdin);
      freopen("error.txt", "w", stderr);
      freopen("output.txt", "w", stdout);
   #endif
   
   ll t=1;
   // cin>>t;
   while(t--)
   {
      solve();
      // cout<<"\n";
   }

   cerr<<"Time Taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
   return 0;
}

int l;
map<vi,int> dp;

int soln(int s,int e,int amt,vi a)
{
   if(amt==0)
      return 0;
   if(s>e or amt<0)
      return l;
   if(dp.find({s,e,amt})!=dp.end())
      return dp[{s,e,amt}];

   int m=1+soln(s+1,e,amt-a[s],a);
   int n=1+soln(s,e-1,amt-a[e],a);

   return dp[{s,e,amt}]=min(m,n);
}

void solve()
{
   int n;
   cin>>n;
   vi a(n);
   for(int i=0;i<n;i++)
      cin>>a[i];
   int x;
   cin>>x;
   l=pow(10,9);

   int ans=soln(0,n-1,x,a);

   if(ans>=l)
      cout<<-1;
   else
      cout<<ans;
}