Simple Java recursive solution


  • 16

    The basic idea is to pick each offer, and subtract the needs. And then compute the price without the offer.
    Pick whichever is minimum.

    Edit : ) much appreciated if someone can shorten the code with Java8 :)

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        int result = Integer.MAX_VALUE;
        //apply each offer to the needs, and recurse
        for(int i = 0; i < special.size(); i++) {
            List<Integer> offer = special.get(i);
            boolean invalidOffer = false;
            for(int j = 0; j < needs.size(); j++) { // subtract offer items from needs
                int remain = needs.get(j) - offer.get(j);
                needs.set(j, remain);
                if(!invalidOffer && remain < 0) invalidOffer = true; // if offer has more items than needs
            }
            if(!invalidOffer) { //if valid offer, add offer price and recurse remaining needs
                result = Math.min(result, shoppingOffers(price, special, needs) + offer.get(needs.size()));
            }
            for(int j = 0; j < needs.size(); j++) { // reset the needs
                int remain = needs.get(j) + offer.get(j);
                needs.set(j, remain);
            }
        }
        // choose b/w offer and non offer
        int nonOfferPrice = 0;
        for(int i = 0; i < needs.size(); i++) {
            nonOfferPrice += price.get(i) * needs.get(i);
        }
        return Math.min(result, nonOfferPrice);
    }
    

    UPDATE 1 : For the below test case, we get time limit exceeded since it's exponential. TLE due to needs=30+.
    I've requested admins to add this testcase.

    [2,5]
    [[1,0,5],[1,2,10]]
    [39,39]
    

    So I made some optimization to reduce the recursive calls, by precomputing the number of times offer can be applied. See UPDATE 3, there's an example that breaks this greedy optimization.

        public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
            int result = Integer.MAX_VALUE;
            //apply each offer to the needs, and recurse
            for(int i = 0; i < special.size(); i++) {
                List<Integer> offer = special.get(i);
                boolean invalidOffer = false;
                int offerCount = Integer.MAX_VALUE; // number of times offer can be applied
                for(int j = 0; j < needs.size(); j++) { // pre-compute number of times offer can be called
                    int remain = needs.get(j) - offer.get(j);
                    if(!invalidOffer && remain < 0) invalidOffer = true; // if offer has more items than needs
                    if(offer.get(j) > 0)
                    offerCount = Math.min(offerCount, needs.get(j)/offer.get(j));
                }
                for(int j = 0; j < needs.size(); j++) { // subtract offer items from needs
                    int remain = needs.get(j) - offer.get(j) * offerCount;
                    needs.set(j, remain);
                }
                if(!invalidOffer) { //if valid offer, add offer price and recurse remaining needs
                    result = Math.min(result, shoppingOffers(price, special, needs) + (offerCount * offer.get(needs.size())));
                }
    
                for(int j = 0; j < needs.size(); j++) { // reset the needs
                    int remain = needs.get(j) + offer.get(j) * offerCount;
                    needs.set(j, remain);
                }
            }
    
            // choose b/w offer and non offer
            int nonOfferPrice = 0;
            for(int i = 0; i < needs.size(); i++) {
                nonOfferPrice += price.get(i) * needs.get(i);
            }
            return Math.min(result, nonOfferPrice);
        }
    

    UPDATE 2: I think OJ is breaking with the below test case. My code handles it though. Expected output is 8000, since it has two items of 1$ each. I've requested to add the test case. Also, another assumption is that result doesn't exceed Integer.MAX_VALUE. @administrators

    [1,1]
    [[1,1,2],[1,1,3]]
    [4000,4000]
    

    UPDATE 3: From @Red_Eden 's thought, I found a test case that breaks my optimization. OJ is missing this test as well. My solution gives answer = 6, but actual is pick one offer just once = 4.

    [500]
    [[2,1],[3,2],[4,1]]
    [9]
    

  • 0
    F

    Concise solution!
    Can you explain your time complexity?


  • 0
    S

    I think the time complexity would be O(n2), am I right?


  • 1

    @fvdcx @SanD
    The time complexity is exponential. The size of this problem is given small, so it works.
    Let's take the max case as an example. You got 6 items, 100 offers and need to buy max 6 items each. At the start point, you have 100 choices and once you pick one offer, there is another 100 choices for the next level. It is a decision tree with 100 branches each level in max. The level of the tree in max is 36. (6 types of items and 6 each in max).


  • 0

    @fvdcx It's definitely exponential.
    The worst case hits when all the offers are valid, which makes it exponential.


  • 1
    R

    @jaqenhgar Thanks for your detailed sharing. I have two questions though. In your UPDATE1, you introduced offerCount to reduce the times of recursion. You buy the highest number of current offer as long as it doesn't give you more than you need and then use the same strategy to buy the next offer as many as possible. It kind of has a touch of a greedy algorithm, but the thing is the special offers are not sorted in any sense. For example, you can fulfill your need by buying 5 offer1 and 1 offer2 or 3 offer1, 1offer2 and 1 offer3. Your algorithm will only buy 5 offer1 and 1 offer2 and wont even try 3 offer1, 12offer2 and 1 offer3(if I understand it right), but there is no guarantee that the latter will cost more. Did i miss anything?

    Another question is I think all solutions posted only compare the cost of buying without any offers or buying with only offers. But since there is a constraint that you cannot buy more than what you need, is it possible that the optimal solution is the combination of both?


  • 0

    @Red_Eden You're absolutely right about the greedy part. My first thought was that the solution might not get accepted, but since it got accepted, I thought your scenario might be redundant. I'll think about it and update again.

    On your second thought, the solution is indeed a combination of both. It did take offers as much as possible, and for the rest of the needs, it considers the price without offer. Say item price is [1,1,1] and offer is [1,1,0,1] and need is [1,1,1].
    If you want to buy without offer, it'll cost you 1+1+1 = 3. But if you consider the offer, you'll get first and second item together for 1$, so the need becomes [0,0,1] for the next iteration, and then the offer is not valid for need [0,0,1]. So it returns non-offer price, which is 1$. So result becomes 1+1 = 2$. After this, it computes non-offer price for all 3 items, which is 1+1+1 = 3$. But min prices is 2$.


  • 3

    @Red_Eden I found the example that breaks my optimization. :)

    [500]
    [[2,1],[3,2],[4,1]]
    [9]
    

    Actual answer is pick each offer once = 1+2+1 = 4$
    My solution goes for picking second offer thrice = 2+2+2 = 6$

    Unfortunately OJ test cases are not enough to catch these. But let me submit one.


  • 0
    W

    a optimization on your solution which make your first answer quick 5 times in the test cases

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
            int result = Integer.MAX_VALUE;
            int k = needs.size();
            for(int i=0;i<special.size();i++){
                List<Integer> spe = special.get(i);
                int isValidSpe = -1;
                
                for(int j=0;j<k;j++){
                    if(needs.get(j)<spe.get(j)){ isValidSpe = j; break;}
                    needs.set(j,needs.get(j)-spe.get(j));
                }
                if(isValidSpe==-1){ 
                    result = Math.min(result,spe.get(spe.size()-1)+shoppingOffers(price,special,needs));
                    isValidSpe = k;
                }
                
                for(int j=0;j<isValidSpe;j++){
                    needs.set(j,needs.get(j)+spe.get(j));
                }
            }
            int noSpePri = 0;
            for(int i=0;i<k;i++)
                noSpePri += needs.get(i)*price.get(i);
            
            return Math.min(noSpePri,result);
        }
    

  • 0
    R

    @jaqenhgar Yea, your solution is the combination of both. I made a mistake.


  • 0
    L

    Python version:

        def shoppingOffers(self, price, special, needs):
            def shopping(price,special,needs, offerIndex):
                if offerIndex == len(special):
                    return sum([price[i]*needs[i] for i in xrange(len(needs))])
                
                currentSpecialOffer = special[offerIndex]
                offerPrice = currentSpecialOffer[-1]
                offerHasMoreItems = False
                needsClone = list(needs)
                for i in xrange(len(currentSpecialOffer[:-1])):
                    if needsClone[i] - currentSpecialOffer[i] < 0:
                        offerHasMoreItems = True
                        break
                    needsClone[i] -= currentSpecialOffer[i]
                if offerHasMoreItems:
                    return shopping(price,special,needs, offerIndex+1)
                else:
                    return min(offerPrice+shopping(price,special,needsClone, offerIndex), shopping(price,special,needs, offerIndex+1))
            
            return shopping(price,special,needs, 0)
    

  • 0
    L
    int shoppingOffers(vector<int>& price, vector<vector<int> >& special, vector<int>& needs) {  // 638
        int cost = inner_product(price.begin(), price.end(), needs.begin(), 0);
        for (int i=0; i<special.size(); i++) {
        	//transform(needs.begin(),needs.end(),special[i].begin(),needs.begin(), minus<int>());
        	bool valid=true;
        	for (int j=0; j<needs.size(); j++)  valid &= (needs[j]-=special[i][j])>=0;
            if(valid) cost = min(cost, shoppingOffers(price, special, needs) + special[i].back());
            transform(needs.begin(),needs.end(),special[i].begin(),needs.begin(),  plus<int>());  // backtrack
        }
        return cost;
    }
    

  • 0
    G

    I think this solution is backtracking.


  • 0
    I

    @Nakanu I can not agree more.so with an orchestrated test case, this problem could not be solved in reasonable time ,right? Is the limit of special offers too high?


  • 0

    @iynaur87 Yes. I guess for this problem, the interviewer just expect this solution. Memorization or DP is not required.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.