Question

Phonepe | OA Coding Questions and Solutions | 2022 | Set-11

Answer 1

IMAGES OF QUES

 

 

Answer 2

Java solution:

 

public static void main(String[] args) {
int[] tanks = {2,5,6,4};
int[][] dealers = {{1,5}, {3,2}, {4,3}};
System.out.println(solve(tanks, dealers));
}

private static int solve(int[] tanks, int[][] dealers) {
Arrays.sort(tanks);
int[] dp = new int[tanks[tanks.length - 1] + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
Map<Integer, Integer> map = new HashMap<>();
for(int[] d : dealers) {
  map.put(d[0], d[1]);
}
for(int i=1;i<dp.length;i++) {
  if(map.containsKey(i)) {
   dp[i] = map.get(i);
  }
  for(int j=0;j<i;j++) {
   if(map.containsKey(j)) {
    dp[i] = Math.min(dp[i], dp[i-j] + map.get(j));
   }
  }
}
int sum = 0;
for(int t : tanks) {
  sum += dp[t];
}
return sum;
}

straightforward dp.
fuelling of each car is independent of another car.
dp[i] -> minimum cost to fill a car with i litres.
dp[i] = Math.min(dp[i-m0] + cost[m0]) for all m <= i can fuel is less than the car tank

Do a bottom up dp till max of car tanks.