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 <= 100^5
1 <= ATM[i] <= 10^5
1 <= X <= 10^5
Its simply, finding the longest subarray having sum = Total sum-X and the answer is N-len
import java.io.*;
import java.util.*;
import java.lang.Math;
class Solution {
public static int minimumWithdrawal(int[] ATM, int left, int right, int X, int steps, int[] strg){
if(X < 0 || left > right) return Integer.MAX_VALUE;
if(X == 0) return steps;
if(strg[X] != -1) return strg[X];
int op1 = minimumWithdrawal(ATM, left + 1, right, X - ATM[left], steps + 1, strg);
strg[X] = op1;
int op2 = minimumWithdrawal(ATM, left, right - 1, X - ATM[right], steps + 1, strg);
strg[X] = Math.min(strg[X], op2);
return strg[X];
}
public static void main(String args[]){
Scanner scan = new Scanner(System.in);
int N;
N=scan.nextInt();
int[] ATM = new int[N];
for(int j=0;j<N;j++){
ATM[j]=scan.nextInt();
}
int X;
X=scan.nextInt();
int result;
int[] strg = new int[X +1];
Arrays.fill(strg, -1);
result = minimumWithdrawal(ATM, 0, N - 1, X, 0, strg);
result = result == Integer.MAX_VALUE ? -1 : result;
System.out.print(result);
return ;
}
}
This code is not passing all the test cases for the problem. Can anyone tell me why ?
is it possible to attach link to original problem statement