package leetcode;

import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.com/problems/shopping-offers/
 */
public class Problem638 {
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        // TODO
        return 0;
    }

    private static void lowestPrice(List<Integer> prices, List<List<Integer>> specials, List<Integer> needs) {
        for (List<Integer> special : specials) {
            int specialPrice = special.get(special.size() - 1);
            // exclude the last element
            boolean foundSpecial = true;
            for (int i = 0; i < special.size() - 1; i++) {
                if (needs.get(0) - special.get(i) < 0) {
                    foundSpecial = false;
                    break;
                }
            }
            if (foundSpecial) {
                for (int i = 0; i < special.size() - 1; i++) {
                    needs.set(i, needs.get(0) - special.get(i));
                }
            }
            lowestPrice(prices, specials, needs);
        }
    }

    public static void main(String[] args) {
        Problem638 prob = new Problem638();
        System.out.println(prob.shoppingOffers(
            Arrays.asList(2, 5),
            Arrays.asList(Arrays.asList(3, 0, 5), Arrays.asList(1, 2, 10)),
            Arrays.asList(3, 2))); // 14
        System.out.println(prob.shoppingOffers(
            Arrays.asList(2, 3, 4),
            Arrays.asList(Arrays.asList(1, 1, 0, 4), Arrays.asList(2, 2, 1, 9)),
            Arrays.asList(1, 2, 1))); // 11
    }
}

@@ -260,32 +260,49 @@
     
-// TODO%0A        return 0
+return lowestPrice(price, special, needs)
 ;%0A  
@@ -325,20 +325,19 @@
  static 
-void
+int
  lowestP
@@ -408,32 +408,69 @@
 teger%3E needs) %7B%0A
+        int min = Integer.MAX_VALUE;%0A
         for (Lis
@@ -728,33 +728,33 @@
   if (needs.get(
-0
+i
 ) - special.get(
@@ -1002,17 +1002,17 @@
 eds.get(
-0
+i
 ) - spec
@@ -1054,29 +1054,39 @@
         
-%7D%0A
     
-       
+min = Math.min(min,
  lowestP
@@ -1110,24 +1110,25 @@
 ials, needs)
+)
 ;%0A        %7D%0A
@@ -1121,25 +1121,467 @@
 ));%0A        
-%7D
+        // backtracking%0A                for (int i = 0; i %3C special.size() - 1; i++) %7B%0A                    needs.set(i, needs.get(i) + special.get(i));%0A                %7D%0A            %7D%0A        %7D%0A        int total = 0;%0A        for (int i = 0; i %3C prices.size(); i++) %7B%0A            int price = prices.get(i);%0A            int num = needs.get(i);%0A            total += (price * num);%0A        %7D%0A        min = Math.min(min, total);%0A        return min;
 %0A    %7D%0A%0A    
@@ -1863,16 +1863,18 @@
 ; // 14%0A
+//
         
@@ -1905,32 +1905,34 @@
 shoppingOffers(%0A
+//
             Arra
@@ -1951,16 +1951,18 @@
  3, 4),%0A
+//
         
@@ -2030,24 +2030,26 @@
  2, 1, 9)),%0A
+//
             

Update problem 638