Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Note: You can assume that

• 0 <= amount <= 5000
• 1 <= coin <= 5000
• the number of coins is less than 500
• the answer is guaranteed to fit into signed 32-bit integer

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10] 
Output: 1

Subscribe to see which companies asked this question.

class Solution {
public:
    int change(int amount, vector<int> coins) {
        /* // Recursive.
        if (amount == 0) {
            return 1;
        }
        if (amount < 0 || coins.size() == 0) {
            return 0;
        }
        int denom = coins[0];
        int factor = 0, sol = 0;
        coins.erase(coins.begin());
        
        while (denom * factor <= amount) {
            sol += change(amount - denom * factor, coins);
            factor++;
        }
        return sol;
        */
        // Dynamic.
        int ch[amount + 1][coins.size() + 1];
        
        for (int i = 0; i < coins.size() + 1; i++) {
            ch[0][i] = 1;
        }
        for (int i = 1; i < amount + 1; i++) {
            ch[i][0] = 0;
        }
        
        for (int i = 1; i < amount + 1; i++) {
            for (int j = 1; j < coins.size() + 1; j++) {
                int sol = 0;
                int factor = 0;
                while (factor * coins[j - 1] <= i) {
                    sol += ch[i - factor * coins[j - 1]][j - 1];
                    factor++;
                }
                ch[i][j] = sol;
            }
        }
        return ch[amount][coins.size()];
    }
};

=====================

/******************************************************************************

                              Online C++ Compiler.

               Code, Compile, Run and Debug C++ program online.

Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>

#include <vector>

#include <map>

using namespace std;

int helper(vector<int>& input, int idx, int target,

            map<string, int>& mp) {

    string key = to_string(idx) + ":" + to_string(target);

    if (mp.count(key) != 0) {

        return mp[key];

    }

    if (idx >= input.size()) {

        mp[key] = 0;

        return 0;

    }

    if (target < 0) {

        mp[key] = 0;

        return 0;

    } else if (target == 0) {

        mp[key] = 1;

        return 1;

    }

    

    int a = helper(input, idx, target - input[idx], mp);

    int b = helper(input, idx + 1, target, mp);

    mp[key] = a + b;

    return a + b;

}

int minWays(vector<int>& input, int target) {

    /*

    - recursive & memoization

    map<string, int> mp;

    int ans = helper(input, 0, target, mp);

    return mp["0:" + to_string(target)];

    */

    

    //- dynamic programming

    if (input.size() == 0) {

        return 0;

    }

    vector<int> dp(target + 1, 0);

    dp[0] = 1;

    

    

    /*

    // This will give total permutations.

    for (int i = 1; i <= target; i++) {

        for (auto value : input) {

            if (i - value >= 0) {

                dp[i] += dp[i - value];

            }

        }

    }

    */

    

    // But what we need is just the combination. So,

    for (auto value: input) {

        for (int i = value; i <= target; i++) {

            dp[i] += dp[i - value];

        }

    }

    return dp[target];

}

int main()

{

    cout<<"Hello World" << endl;

    

    vector<int> input;

    int target;

    // Test case 1:

    input = {1, 2, 5};

    target = 0;

    cout << minWays(input, target) << endl;

    

    // Test case 2:

    input.clear();

    input = {};

    target = 5;

    cout << minWays(input, target) << endl;

    

    // Test case 3:

    input.clear();

    input = {1, 2, 5};

    target = 5;

    cout << minWays(input, target) << endl;

    

    // Test case 4:

    input.clear();

    input = {1, 5, 15};

    target = 125;

    cout << minWays(input, target) << endl;

    

    return 0;

}

Poor Pigs.

There are 1000 buckets, one and only one of them contains poison, the rest are filled with water. They all look the same. If a pig drinks that poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket contains the poison within one hour.

Answer this question, and write an algorithm for the follow-up general case.

Follow-up:

If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the "poison" bucket within p minutes? There is exact one bucket with poison.

Solution:

class Solution {

public:

    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {

        // one pig can identify 5 buckets.

        // 2 pig can identify 5 X 5 buckets.

        // 3 pig can identify 5 X 5 X 5 buckets.

        // and so on..

        int pig = 0;

        int linear_bucket_count = minutesToTest/minutesToDie + 1;

        while (pow(linear_bucket_count, pig) < buckets) {

            pig++;

        }

        

        return pig;

    }

};

Beautiful Arrangement

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 ≤ i ≤ N) in this array:

1. The number at the ith position is divisible by i.
2. i is divisible by the number at the ith position.

Now given N, how many beautiful arrangements can you construct?

Example 1:

Input: 2
Output: 2
Explanation: 

The first beautiful arrangement is [1, 2]:

Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).

Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).

The second beautiful arrangement is [2, 1]:

Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).

Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.

Note:

1. N is a positive integer and will not exceed 15.

static int countArrangements(int n,int[] data){
    if(n<=0){
      return 1;
    }
    int count = 0;
    for(int i=0;i<n;++i){

      // Just check if any number can be placed at n index.
      if(data[i]%n == 0 || n%data[i] ==0){
        swap(data,i,n-1);
        count += countArrangements(n-1,data);
        swap(data,i,n-1);
      }
    }
    return count;
  }

  static void swap(int[] data,int i,int j){
    int temp = data[i];
    data[i] = data[j];
    data[j] = temp;
  }

  static int arrangements(int n) {
    int[] data = new int[n];
    for(int i=0;i<n;++i){
      data[i] = i+1;
    }
    return countArrangements(n,data);
  }