Java recursive solution 3ms


  • 12
    Q
    public class Solution {
        int total = Integer.MAX_VALUE;
        public int coinChange(int[] coins, int amount) {
            if (amount == 0) return 0;
    		Arrays.sort(coins);
    		count(amount, coins.length-1, coins, 0);
    		return total == Integer.MAX_VALUE?-1:total;
        }
    	void count(int amount, int index, int[] coins, int count){
    		if (index<0 || count>=total-1) return;
    		int c = amount/coins[index];
    	    for (int i = c;i>=0;i--){
    			int newCount = count + i;
    			int rem = amount - i*coins[index];
    			
    			if (rem>0 && newCount<total)
    			    count(rem, index-1, coins, newCount);
    			else if (newCount<total)
    			    total = newCount;
    			else if (newCount>=total-1)
    				break;
    		}
    	}
    }

  • -1
    F
    This post is deleted!

  • 0

    I just tested your test case the above code does return the expected answer, which is 3. Could you please list another test case? Thanks.


  • 0
    Q

    Why do those lines make no sense? If we find a new count that's lower than current min coin count, we update the miminum coin count to new value.
    And what do you mean 'by accident'. All 180 tests were passed by my code by accident? Really?!


  • 1
    Q

    Slightly modifed version, may be this one will make more sense.

       
    public class Solution {
        int total = Integer.MAX_VALUE;
        public int coinChange(int[] coins, int amount) {
           	Arrays.sort(coins);
    		count(amount, coins.length-1, coins, 0);
    		return total == Integer.MAX_VALUE?-1:total;
        }
    	void count(int amount, int index, int[] coins, int count){
    		if (index>=0 && count<total-1)
        		for (int i = amount/coins[index];i>=0;i--){
        			int rem = amount - i*coins[index];
        			int newCount = count + i;
        			if (rem>0 && newCount<total) 
        			    count(rem, index-1, coins, newCount);
        			else{
        			    total = newCount<total?newCount:total;
        			    break;
        			}
        		}
    	}
    }
    </code>
    

  • 0
    F

    sorry man, I misread the code, this should be a fast and correct answer.


  • 8
    Q

    After taking a look at the problem again was able to bring down the running time from 4-5 ms down to 3 ms

    public class Solution {
        int minCount = Integer.MAX_VALUE;
        public int coinChange(int[] coins, int amount) {
           	Arrays.sort(coins);
    		count(amount, coins.length-1, coins, 0);
    		return minCount == Integer.MAX_VALUE?-1:minCount;
        }
    	void count(int amount, int index, int[] coins, int count){
    	    if (index<0 || count+2>minCount) return;
    		for (int i = amount/coins[index];i>=0;i--){
    			int newAmount = amount - i*coins[index];
    			int newCount = count + i;
    			if (newAmount>0 && newCount+1<minCount) 
    			    count(newAmount, index-1, coins, newCount);
    			else{
    			    if (newAmount==0 && newCount<minCount)
    			        minCount = newCount;
    			    break;
    			}
    		}
    	}
    }

  • 0
    P

    The solution fails this case
    [1]
    2147483647

    which isn't in original test case. But can be easily fixed anyway.


  • 0
    Q

    Fixed, btw online judge is failing this test. I don't think it's due to it being Integer.MAX_VALUE but due to it's use of DP which is way too slow.

    
    public class Solution {
        long minCount = Long.MAX_VALUE;
        public int coinChange(int[] coins, int amount) {
            Arrays.sort(coins);
            count(amount, coins.length-1, coins, 0);
            return minCount == Long.MAX_VALUE?-1:(int)minCount;
        }
    
    

  • 1
    J

    Good solution. Based on your solution I did some more optimization. It run even faster (2ms):

    public class Solution {
     	int minCount = Integer.MAX_VALUE;
    
    	public int coinChange(int[] coins, int amount) {
    		Arrays.sort(coins);
    		count(amount, coins.length - 1, coins, 0);
    		return minCount == Integer.MAX_VALUE ? -1 : minCount;
    	}
    
    	void count(int amount, int index, int[] coins, int count) {
    		if(amount % coins[index] == 0) {
    			int newCount = count + amount / coins[index];
    			if(newCount < minCount)
    				minCount = newCount;
    		}
    		
    		if(index == 0)
    			return;
    			
    		for (int i = amount / coins[index]; i >= 0; i--) {
    			int newAmount = amount - i * coins[index];
    			int newCount = count + i;
    			
    			int nextCoin = coins[index-1];
    			if(newCount + (newAmount + nextCoin -1) / nextCoin >= minCount)
    				break;
    			
    			count(newAmount, index - 1, coins, newCount);
    		}
    	}
    }
    

  • 0
    S
    public class Solution {
        static int minCount = 0;
        public int coinChange(int[] coins, int amount) {
            if(amount == 0) return 0;
    		else if (amount >= Integer.MAX_VALUE) return -1;
    		Arrays.sort(coins);
    		count(coins,amount,coins.length-1);
    		return minCount;
        }
       private static void count(int[] coins, int amount, int index) {
    	minCount+=amount/coins[index];
    	amount=amount%coins[index];
    	if(amount==0 || index == 0)
    		return;
    	else
    		count(coins,amount,index-1);
        }
    }
    

    For some strange reasons, this is NOT passing the validator. I have tried as much as possible to write the least minimum code to achieve the objective.


  • 1
    S

    can you explain why you need "-1" in
    if(newCount + (newAmount + nextCoin -1) / nextCoin >= minCount)
    break;
    ?


  • 0
    Z

    cool pruning.


  • 1
    A

    @sandiegosd I tried this:
    if(newCount + newAmount / nextCoin >= minCount) break;
    And the system gives an accept.
    I'm also curious about why to use (newAmount + nextCoin -1).

    And I think the reason why this is much faster than the usual DP-bottom up/top down is that:
    We define
    F(S)=F(S−C)+1
    (F(S) - minimum number of coins needed to make change for amount S using coin denominations [ c0 … c(n−1) ]. )
    And his solution is :
    F[S] = F[S - C * i] + i (0<= i <= S/C)

    The 1st calculate every amount, and the 2nd only consider the possible amount.

    And also he sorted the coins array, so we can break as soon as we know it's impossible to have a smaller counts.


  • 0

    Can you give some hint how to came out this amazing solution?


  • 0

    @zhugejunwei

    Nice, I think it is more like greedy algorithm.


Log in to reply
 

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