Coin Change Problem

 #include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// recursive

int count(vector<int> &coins, int m, int n) {

    if (n == 0) 

        return 1;

    if (n < 0)

        return 0;

     if (m <= 0 && n >= 1)

        return 0;

    return count(coins, m-1, n) + count(coins, m, n-coins[m-1]);

}

// recursive with memoization

unsigned long dp[51][251];// global array initialized to 0 

unsigned long countDP1(vector<int> & coins,  int i, int n)

{

    if(n == 0)

        return 1; //no coins

    if(n < 0) 

        return 0; //no negative money      

    if(i == coins.size()) //no more options of coins

        return 0;

    if(dp[i][n]!=0)

        return dp[i][n];

        //leave it or take it

    return dp[i][n] = countDP1(coins,i+1, n) + countDP1(coins,i, n-coins[i]);

}

//loop with 2D memoization space O(n*m) time O(n*m)

unsigned long countDP2(vector<int> &coins, int m, int n ) 

{ 

    int i, j; 

    unsigned long table[n + 1][m],  x, y; 

    for (i = 0; i < m; i++) 

          table[0][i] = 1;  

     for (i = 1; i < n + 1; i++) 

    { 

        for (j = 0; j < m; j++) 

        { 

            // Count of solutions including coins[j] 

            x = (i-coins[j] >= 0) ? table[i - coins[j]][j] : 0; 

            // Count of solutions excluding coins[j] 

            y = (j >= 1) ? table[i][j - 1] : 0; 

            // total count 

            table[i][j] = x + y; 

        } 

    } 

    return table[n][m - 1]; 

}

// loop with 1D memoization space O(n) time O(n*m)

unsigned long countDP( vector<int> &coins, int m, int n ) 

{ 

      unsigned long table[n + 1]; 

    memset(table, 0, sizeof(table)); 

      table[0] = 1; 

      for(int i=0; i< m; i++) 

        for(int j=coins[i]; j <= n; j++) 

            table[j] += table[j-coins[i]]; 

      return table[n]; 

} 

// Complete the ways function below.

unsigned long ways(int n, vector<int> coins) {

    return countDP(coins, coins.size(), n);

    //return countDP1(coins, 0, n);

}

int main()

{

    ofstream fout(getenv("OUTPUT_PATH"));

    string nm_temp;

    getline(cin, nm_temp);

    vector<string> nm = split_string(nm_temp);

    int n = stoi(nm[0]);

    int m = stoi(nm[1]);

    string coins_temp_temp;

    getline(cin, coins_temp_temp);

    vector<string> coins_temp = split_string(coins_temp_temp);

    vector<int> coins(m);

    for (int i = 0; i < m; i++) {

        int coins_item = stoi(coins_temp[i]);

        coins[i] = coins_item;

    }

    unsigned long res = ways(n, coins);

    fout << res << "\n";

    fout.close();

    return 0;

}

vector<string> split_string(string input_string) {

    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {

        return x == y and x == ' ';

    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {

        input_string.pop_back();

    }

    vector<string> splits;

    char delimiter = ' ';

    size_t i = 0;

    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {

        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;

        pos = input_string.find(delimiter, i);

    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;

}

Subset of non-adjacent elements with the maximum sum

int maxSubsetSum(vector<int> arr) {
    int cmax = 0, curr_plus_previous_not_adj;

    int previous_not_adj = arr[0];
    int previous_adj = max(arr[1], previous_not_adj);

    for(int i = 2; i < arr.size(); i++) {
            curr_plus_previous_not_adj = max(arr[i], arr[i] + previous_not_adj);
            cmax = max(curr_plus_previous_not_adj, previous_adj);
            previous_not_adj = previous_adj;
            previous_adj = cmax;
    }
    return cmax;
}

Fibonacci - Dynamic Programming + Optmized versions

f (1) = 1

f (2) = 1

f (3) =  f(1) + f (2)

f (4) =  f(2) + f (3)

f (n) =  f(n-2) + f(n-1)

         f(1)        f(2)

            \         /   |

              f(3)      |

                |    \    |

                |     f(4)

                |     /   |         

                f (5)   |

                  |    \  |

                  |    f(6)

                  |     /

                 f(7)

To solve the fibonacci problem the naive solution is simple as the following

unsigned long fibonacci(int n) {

        if (n < 2)

                return 1;

        return  fibonacci(n-2) + fibonacci(n-1);

}

Using the naive recursive approach we will end up doing the same recursive call more than once, for example to calculate to calculate f(4) and f (3), we calculate f(2) , to calculate f(4) and f(5) we calculate f(3), to calculate f(5) and f(6) we use f(4) and so on.

T(n) = T(n-1) + T(n-2) + c
= 2T(n-1) + c //from the approximation T(n-1) ~ T(n-2)
= 2*(2T(n-2) + c) + c
= 4T(n-2) + 3c
= 8T(n-3) + 7c
= 2^k * T(n - k) + (2^k - 1)*c

Let's find the value of k for which: n - k = 0
k = nT(n) = 2^n * T(0) + (2^n - 1)*c
= 2^n * (1 + c) - c

The complexity time of this algorithm will be  O (2^n)

Using Dynamic programming (recursion + memoization) we can reduce this time, simply saving already calculated results in a dictionary and avoid repetitive recursion calls by just consulting the dictionary.

The Dynamic programming version of fibonacci that runs in O(n) time.

unsigned long fibonacci(int n, unordered_map<unsigned long,unsigned long> &map) {

        if (map.find(n) != map.end()) {

                return map[n];

        }

        if (n < 2)

                return 1;

        map[n] = fibonacci(n-2, map) + fibonacci(n-1, map);

        return map[n];

}

Optimized version saving space

Time: O(n) , Space O(1)

int fib(int n)
{
    int a = 0, b = 1, c, i;
    if( n == 0)
            return a;
    for(i = 2; i <= n; i++)
    {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
} 

And finally the most optmized version of fibonacci,

Time: O(1) , Space(1)

int fib(int n) {
double phi = (1 + sqrt(5)) / 2;
return round(pow(phi, n) / sqrt(5));
}

Overflow problem - Curious case case of Binary Search

https://thebittheories.com/the-curious-case-of-binary-search-the-famous-bug-that-remained-undetected-for-20-years-973e89fc212

When calculating the mid position in the array

This operation can result in a overflow problem when low + high is too much high

mid = (low + high) / 2;

Replacing by this operation we no longer have the same problem
mid = low + (high - low)/2;


.............................................
Other example of overflow problem
int x = 256;
int y = 256;

unsigned long  result;
result = x * 256 * 256 + y*256*256;
the result of the operation will be calculated with size of the highest operand that is integer, and 256 * 256 is already the maximum value of a integer, multiplied by an integer with value 256, the result will not fit in Integer space.

To fix this, we increase the size of the highest operando
result = x * 256 * 256ul + y*256*256ul;
or
result = ((unsigned long)x) * 256 * 256 + ((unsigned long)y)*256*256;

Sorting Agorithms Animation

Clever way of checking if number is prime

The solution relies on showing that p² - 1 is a multiple of 2x2x2x3

First   
p² - 1 = (p - 1) x (p + 1)

p must be odd, so p - 1 and p + 1 must be even. We have two of the factors we require.

Since p - 1 and p + 1 effectively form 2 consecutive even numbers one of them must be a multiple of 4, thus we have another of our factors of 2.
So far we have 2x2x2, now to get the factor of 3

p - 1, p & p + 1 form three consecutive numbers. In any three consecutive numbers one will be a multiple of 3, we know it is not p which is a multiple of 3, as this is prime, hence either p - 1 or p + 1 is a multiple. Therefore p² - 1 has the factors 2, 2, 2 & 3 hence:

p² - 1 = 24n

(Why must p be greater than 3? Well 3 is the only number which is both a multiple of 3 and prime)

* - I know 2 is prime, and even. But we are in the space greater than 3

bool isPrimeOrNot(int num) {

if (num < 0) return false;

if (num == 0 || num == 1) return false;

if (num == 2 || num == 3) return true;

if ((num * num - 1) % 24 == 0) return true;

return false;
}

Read more: http://www.java67.com/2014/01/how-to-check-if-given-number-is-prime.html#ixzz5UtLjP0dX

Complexity of Algorithms - Why O (Logn) ?

n = 8

|1|2|3|4|5|6|7|8|                                -  I have n  elements in yellow color

n/21                                                  -  I divide n in half (by 2)

|1|2|3|4|        |5|6|7|8|                       -  Now I have n/2

n/22                                                 -  I divide n/2 in half (by 2)

|1|2|   |3|4|      |5|6|      7|8|                -  Now I have n/22 

n/23                                                 -  I divide n/22  in half (by 2) 2

|1|  |2|   |3|   |4|  |5|  |6|   |7|    |8|     -  Now I have n/23  =  1  element in yellow color

I divided by 2, 3 times that is the number of interaction in a loop or recursion of our algorithm
but if n was bigger or shorter we would generically divide it by x

x = number of interactions or division of our problem in the half
n /(2x) = 1     - after x divisions we have only 1  left
n = 2x          - we apply logarithm in base 2 in both sides
log2n = log22x  
log2n = xlog22  - log22 = 1
log2n = x       - from here we get that the number of interactions is log2n or simple log n