Count number of ways to reach a given score in a game

Consider a game where a player can score 3 or 5 or 10 points in a move. Given a total score n, find number of ways to reach the given score.

The idea is to create a table of size n+1 to store counts of all scores from 0 to n. For every possible move (3, 5 and 10), increment values in table and it can be solved in O(n) time and O(n) auxiliary space.

Following is the implementation in C++

#include<iostream>

#include<vector>

#include<algorithm>

using namespace std;

int main(){

    int n;

    cout<<"Enter the score"<<endl;

    cin>>n;

    vector<int> v(n+1,0);

    v[0] = 1;

    for(auto i = 3;i!=v.size();++i){

        v.at(i)+=v.at(i-3);

    }

    for(auto i = 5;i!=v.size();++i){

        v.at(i)+=v.at(i-5);

    }

    for(auto i = 10;i!=v.size();++i){

        v.at(i)+=v.at(i-10);

    }

    cout<<*(v.end()-1);

    return 0;

}

You can change the value of the points in the game by changing the value of variable i in the three for loops...Enjoy the game!

Partition Problem - Karmarkar Karp Algorithm

This is an implementation of the Karmarkar-Karp algorithm in O(nlogn) steps.

The Karmarkar-Karp heuristic begins by sorting the numbers in decreasing order. At each step, the algorithm commits to placing the two largest numbers in different subsets, while differencing the decision about which subset each will go in. The algorithm continues removing the two largest numbers, replacing by their difference in the sorted list, until there is only one number left, which is the value of the final subset difference. If the final subset difference is equal to 0, then partition is possible else not possible.

Following is the implementation of the algorithm in C++ and note that this algorithm better than the Dynamic Programming Approach because Dynamic approach takes longer time for large value of sum.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
   vector<int>v={3, 1, 1, 2, 2, 1};
   sort(v.begin(),v.end());
   int a;
   while(v.size()!=1){
        auto i = v.end()-1;
        a = (*(i))-(*(i-1));
        v.pop_back();
        v.pop_back();
        v.push_back(a);
        sort(v.begin(),v.end());
   }
   if (a==0)
        cout<<"Partition is Possible";
    else
        cout<<"Partition is not Possible";


}
I will soon update the code of the algorithm, so that you can also find the two subsets partition elements. Till then enjoy the game of partitions.

The Longest Increasing Subsequence

Hi Guys,How are you doing? I have a wonderful news, I tried to solve one of the Dynamic Problem
The Longest Increasing Subsequence. And the wonderful thing about this is that I have solved it in O(n log n) time , yes you heard it right! better than the Dynamic Programming approach which took O(n^2).  I have implemented the concept of PATIENCE SORTING . So What are you waiting for ?get yourself equipped with the best approach to solve Longest Increasing Sub sequence.

Following is the C++ code of the Problem:

#include<iostream>
#include<vector>
#include<algorithm>;

using namespace std;
int main(){
    vector<int>a={7,2,8,1,3,4,10,6,9,5};
    int sz = a.size();
    vector<int> b(sz, 0);
    vector<int> c(sz,0);
    c[0]=1;
    b[0]=a[0];
    for(auto i = 1;i!=a.size();++i){
        for(auto j=0;j<b.size();++j)
        if (a.at(i)>=b.at(j)){
            b[j]=a[i];
            c[j]=c[j]+1;
            break;
        }
    }
    cout<< *(max_element(c.begin(), c.end()));
}

Note: The above given algorithm may give erroneous results if you use consecutive equal values in the sequence. So, do avoid it, Or the best way is to optimize the code and Notify me in the comments below. Wishing you  "Ever Increasing Sequence of Happiness!"

LONGEST PALINDROMIC SUBSEQUENCE

Hello Guys! Well! Do you know that I am on a quest of solving Dynamic Problems? And yes they have freaked me out. But nevertheless I am thoroughly enjoying the beauty of Dynamic Programming. So, I present to you yet another DP,  LONGEST PALINDROMIC SUBSEQUENCE

Problem Statement: Given a sequence, find the length of the longest palindromic sub sequence in it. For example, if the given sequence is “BBABCBCAB”, then the output should be 7 as “BABCBAB” is the longest palindromic sub sequence in it. “BBBBB” and “BBCBB” are also palindromic subsequences of the given sequence, but not the longest ones.

Another very important note: I have implemented the code in C++, I have  made it a lot easier and understandable than the rest of the general solutions on the web.

#include<iostream>

using namespace std;

int main(){

    string s ("BBABCBCAB");

    size_t l = (s.size())-1;

    int T[l][l],j,k=1;

    for(auto i = 0;i<=l;++i)

        T[i][i]=1;

    while(k<=l){

        for(auto i = 0;i<=l-k;++i){

            j = i+k;

            if (s.at(i)==s.at(j))

               T[i][j]= T[i+1][j-1] + 2;

            else

               T[i][j]= max(T[i][j-1], T[i+1][j]);

        }++k;

    }return T[0][l];

}

The Code looks Sweet, Simple and Short Isn't It? I won't brag about myself I leave that on to you.

Knapsack Problem

Problem Statement : Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Lets take an example: The limit given to us is 7

  weight ,value

   1             1 

   3             4

   4             5

   5             7

weight      0    1    2    3    4    5    6    7

(1) 1         0    1    1    1     1    1    1    1

(4) 3         0    1     1    4    5    5    5    5 

(5) 4         0    1     1    4    5    6    6    9

(7) 5         0     1    1    4    5    7    8    9

Finally the answer in the above 2-D array[n][limit] = 9,    where n = 4 and limit = 7.

So the Time Complexity of Knapsack problem using Dynamic Programming turns out to be O(NW)

Following is a C++ implementation in C++. There is no scope of any modification in the code of the problem, it is same as every other code that is up on the web. 

// A Dynamic Programming based solution for 0-1 Knapsack problem
#include<stdio.h>

// A utility function that returns maximum of two integers,You can even use the Library Max function
int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[n+1][W+1];

// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}

return K[n][W];
}

int main()
{
int val[] = {8,4,0,5,3};
int wt[] = {1,2,3,2,2};
int W = 4;
int n = sizeof(val)/sizeof(val[0]);
printf("%d", knapSack(W, wt, val, n));
return 0;
}

Marie Binet loved Fibonacci..

All of us in our lifetime have once stumbled upon the problem of calculating Fibonacci Number. Did you know that about the famous Binet's Formula, with the help of which you can easily calculate nth Fibonacci Number. 

         

So to accurately calculate Fibonacci numbers using Binet's formula, you need an accurate interpretation of √5. Since √5 is irrational, it cannot be accurately represented using double or float, hence Binet's formula doesn't work with these types (however, the rounding in the computation leads to exact results for some small inputs). Since the Fibonacci numbers are integers, you can get exact results from Binet's formula using double or float for more arguments by rounding afterwards,That will return the correct result for almost all n small enough that the result can be exactly represented as a double. These aren't many, however. 

A double typically has only 53 bits of precision, so only Fibonacci numbers smaller than 2⁵³ can be exactly represented as a double (plus a few larger ones divisible by sufficiently high powers of 2). The last Fibonacci number smaller than 2⁵³ is F(77), but F(78) is divisible by 8, so also exactly representable as a double with 53 bits of precision. However, the above produces correct results only for n <= 70 here, from 71 on, the rounding error is too large (incidentally, the result of Binet's formula using doubles is always too large here, so using floor instead of round would produce the correct result also for F(71), but no further).

With the standard datatypes, not many Fibonacci numbers are exactly representable, the last to fit in an (unsigned) 64 bit type is F(93); for 128 bits, the last is F(186). 

Following is the C++ implementation of Binet's formula to find the nth Fibonacci Number

#include<iostream>

#include<cmath>

using namespace std;

double binet(unsigned int n)

{

    static const double phi = (1 + sqrt(5))*0.5;

    double fib = (pow(phi,n) - pow(1-phi,n))/sqrt(5);

    return round(fib);

}

int main(){

    cout<<binet(n);

    return 0;

}

I you want to read more on generating, click the following Fibonacci Number. However, finding large Fibonacci Number does not have any major practical significance.

Find all the Inversions in an Array

Hello Guys!  Finding all the Inversions in an array is quite a popular problem. I have implemented Merge Sort to solve the problem, it takes  ‎O(n log n) time. 

The code Below in C++ lets you Print all the Inversions in an Array..So, what are you waiting for, go ahead and find all the Inversions in array of your choice.

#include<iostream>
#include<algorithm>
#include<vector>
#include<array>
using namespace std;

void merge(vector<int>& array, vector<int>& array1, vector<int>& array2) {
    array.clear();

    int i, j, k,l;
    for( i = 0, j = 0, k = 0; i < array1.size() && j < array2.size(); k++){
        if(array1.at(i) <= array2.at(j)){
            array.push_back(array1.at(i));
            i++;
        }else if(array1.at(i) > array2.at(j)){
            for(l=i;l!=array1.size();++l){
                cout<<array1.at(l)<<" "<<array2.at(j)<<endl;
            }
            array.push_back(array2.at(j));
            j++;
            l=0;
        }
        k++;
    }
    while(i < array1.size()){
        array.push_back(array1.at(i));
        i++;
    }
    while(j < array2.size()){
        array.push_back(array2.at(j));
        j++;
    }
}

void merge_sort(vector<int>& array) {
    if (1 < array.size()) {
        vector<int> array1(array.begin(), array.begin() + array.size() / 2);
        merge_sort(array1);
        vector<int> array2(array.begin() + array.size() / 2, array.end());
        merge_sort(array2);
        merge(array, array1, array2);
    }
}
int main(){
    vector<int>v = {1, 20, 6, 4, 5};
    merge_sort(v);
    for(int &x:v)
        cout<<x<<" " ;
    return 0;

} 

Note: The following code sorts the input array, if you don't want to change the input array then run the code on the copy of input array.

If you need any clarifications, Please don't hesitate to poke me in the comments below.                                                                   Wishing You  "HAPPY INVERSIONS".

Horner's Rule

Hi! Friends, Whatzz up? I haven't got something special for you today. But it is a problem that you must have encountered in your High School, then why not write code for it? So lets get started!

Horner's rule for evaluating a polynomial:

P(x)=∑k=0nakxk==a0+x(a1+x(a2+⋯+x(an−1+xan)⋯))

given the coefficients a0,a1,…,an and a value for x:

Horner’s method can be used to evaluate polynomial in O(n) time. To understand the method, let us consider 

3x^3 - 5x^2 + 4x - 8. The polynomial can be evaluated as ((3x – 5)x + 4)x – 8. The idea is to initialize result as coefficient of x^n which is 3 in this case, repeatedly multiply result with x and add next coefficient to result. Finally return result.

Following is the C++ implementation of Horner''s Rule:

#include <iostream>

using namespace std;

int horner(int a[], int n, int x)

{

int y = a[0];

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

y = y*x + a[i];

    return y;

}

int main()

{

//  Evaluating value of 3x3 - 5x2 + 4x - 8 for x = 3

int a[] = {3, -5, 4, -8};

int x = 3;

int n = sizeof(a)/sizeof(a[0]);

cout << "Value of polynomial is eual to " << horner(a, n, x);

return 0;

}

CLRS: 2.3-7*

★ Describe a Θ(nlgn)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exists two elements of S whose sum is exactly x.

#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>

using namespace std;

int main(){
    vector<int>v = {2,1,4,5,8,9,2,6};
    int number,j=1;
    cout<<"Enter the Number";
    cin>>number;
    sort(v.begin(),v.end());
    for(auto &i:v){
        if (binary_search(v.begin()+j, v.end(), (number-i))){
            cout<<"Found The two numbers whose sum is exactly equal to"<<number<<endl
                <<i<<" and "<<number-i;
            break;
        }
        ++j;
    }
    return 0;
}

 There is something special about this post. That special thing is the variable j . Try to run the code by omitting the variable j and taking number = 2 . You will get surprising results! Not surprising results, I would rather call it subtly wrong error.  If you find the post to be interesting, Please do write your review in the comments down below. For regular updates Subscribe to the Blog.