Fibonacci Series Using Dynamic Programming in C++

Fibonacci Series Using Dynamic Programming

#include<iostream>
#include<vector>
using namespace std;
int fibo(int n)
{

    vector<int> f(n,0) ;
    //int f[n];
    if(n<=1)
    {
        return n;
    }
    else{
        f[0]=0;
        f[1]=1;
        cout<<f[1];
        for(int i=2;i<=n;i++)
        {
            f[i]=f[i-2]+f[i-1];
        }
        return f[n];
    }
}
int main()
{
    int n;
    cout<<"Enter the rangehhhh:=";
    cin>>n;
    int result=fibo(n);
    cout<<"\n\tThe fibonacci series upto "<<n<<" ="<<result;
    return 0;
}

 

Source code : download source code from here

Output :

Job sequencing with deadlines -Greedy Method Using C

Job Sequencing

#include<stdio.h>

#include<conio.h>

int profit[50],deadline[50],select[50];

void job(int n,int max)

{

int i,j,temp,total=0;

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

{

for(j=0;j<n-i;j++)

{

if(profit[j]<=profit[j+1])

{

temp=profit[j];

profit[j]=profit[j+1];

profit[j+1]=temp;

temp=deadline[j];

deadline[j]=deadline[j+1];

deadline[j+1]=temp;

}

}

}//sorting end

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

{

if(deadline[i]<=max)

{

for(j=deadline[i];j>=1;j--)

{

if(select[j]!=1)

{

select[j]=1;

total+=profit[i];

break;

}

}

}

}

printf("\nTotal profit :=%d",total);

}

void main()

{

int i,n,max=0;

clrscr();

printf("\tEnter no of jobs :=");

scanf("%d",&n);

printf("\nEnter profit and deadline :=");

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

{

printf("\np[%d]:=",i);

scanf("%d",&profit[i]);

printf("d[%d]:=",i);

scanf("%d",&deadline[i]);

select[i]=0;

if(deadline[i]>=max)

max=deadline[i];

}

job(n,max);

getch();

}

Source code: https://github.com/shouvik126/Job-sequencing--Greedy-method

Output:

Knapsack Problem - Greedy Method Using C

Knapsack Problem - Greedy Method Using C

#include<stdio.h>

#include<conio.h>

int profit[50],weight[50],max_weight;

void knapsack(int profit[],int weight[],int n)

{

int i,j;

float max_profit=0.0,temp,p_w[50],select[50];

for(i=0;i<n;i++)//calculating per weight profit

{

p_w[i]=(profit[i]*1.0)/weight[i];

select[i]=0;

}

for(i=1;i<n;i++)//sorting according to per weight profit

{

for(j=0;j<n-i;j++)

{

if(p_w[j]<=p_w[j+1])

{

temp=p_w[j];

p_w[j]=p_w[j+1];

p_w[j+1]=temp;

temp=weight[j];

weight[j]=weight[j+1];

weight[j+1]=temp;

temp=profit[j];

profit[j]=profit[j+1];

profit[j+1]=temp;

}

}

}

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

{

printf("%d,",weight[i]);

}

printf("\n\n");

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

{

if(weight[i]<=max_weight)

{

select[i]=1.0;

max_weight-=weight[i];

}

else

{

select[i]=(max_weight*1.0)/weight[i];

break;

}

}

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

{

max_profit+=(select[i]*profit[i]);

}

printf("\nMaximum profit:=%f",max_profit);

}

void main()

{

int n,i;

clrscr();

printf("\tEnter no of object:=");

scanf("%d",&n);

printf("Enter profit and weight of all the objects:=");

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

{

printf("\nProfit[%d] :",i+1);

scanf("%d",&profit[i]);

printf("\nWeight[%d] :",i+1);

scanf("%d",&weight[i]);

}

printf("\nEnter max weight of knapsack:=");

scanf("%d",&max_weight);

knapsack(profit,weight,n);

getch();

}

Source code: https://github.com/shouvik126/Knapsack-Problem---Greedy-method

Output:

Matrix Multiplication using C

Matrix Multiplication

#include<stdio.h>

#include<conio.h>

int a[20][20],b[20][20],c[20][20];

void main()

{

int i,j,k,n;

clrscr();

printf("\nEnter the order of Matrix(order of 2):=");

scanf("%d",&n);

printf("\nEnter first matrix:=\n");

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

{

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

{

printf("A[%d][%d]:=",i,j);

scanf("%d",&a[i][j]);

}

}

printf("\nEnter second matrix:=\n");

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

{

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

{

printf("B[%d][%d]:=",i,j);

scanf("%d",&b[i][j]);

}

}

clrscr();

printf("\nMatrix A :=\n");

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

{

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

{

printf("%d ",a[i][j]);

}

printf("\n");

}

printf("\nMatrix B :=\n");

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

{

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

{

printf("%d ",b[i][j]);

}

printf("\n");

}

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

{

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

{

c[i][j]=0;

for(k=0;k<n;k++)

{

c[i][j]+=a[i][k]+b[k][j];

}

}

}

printf("\nMultiplication of two matrix A*B=C :=\n");

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

{

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

{

printf("%d ",c[i][j]);

}

printf("\n");

}

getch();

}

Source code: =https://github.com/shouvik126/matrix-multiplication

Output: =

Quick Sort using C

Quick Sort

#include<stdio.h>

#include<conio.h>

int ar[20];

int partition(int low ,int high)

{

int temp,pivot=ar[low],i=low,j=high;

while(i<j)

{

do

{

i++;

}while(ar[i]<=pivot);

do

{

j--;

}while(ar[j]>pivot);

if(i<j)

{

temp=ar[i];

ar[i]=ar[j];

ar[j]=temp;

}

}

temp=ar[low];

ar[low]=ar[j];

ar[j]=temp;

return j;

}

void quick_sort(int low,int high)

{       if(low<high)

{       int i,pivot;

pivot=partition(low,high);

quick_sort(low,pivot);

quick_sort(pivot+1,high);

}

}

void main()

{

int n,i;

clrscr();

printf("Enter how mauny no u want to enter:=");

scanf("%d",&n);

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

{

printf("A[%d]",i+1);

scanf("%d",&ar[i]);

}

ar[n]=9999;//assume as a infinity

printf("\nBefore sorting:=\n");

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

{

printf("%d,",ar[i]);

}

quick_sort(0,n);

printf("\nAfter sorting:=\n");

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

{

printf("%d,",ar[i]);

}

getch();

}

Souce code :=https://github.com/shouvik126/quick-sort

Output: =

Merge Sort using C

Merge Sort

       #include<stdio.h>
#include<conio.h>
int ar[20];
void merge(int low ,int mid,int high)
{
int i=low,j=mid+1,k=0,b[20];
while(i<=mid &&j<=high)
{
if(ar[i]<ar[j])
{
b[k++]=ar[i++];
}
else
{
b[k++]=ar[j++] ;
}
}
for(;i<=mid;i++)
b[k++]=ar[i];
for(;j<=high;j++)
b[k++]=ar[j];
for(i=low,k=0;i<=high;i++,k++)
{
ar[i]=b[k] ;
}
}
void mergesort(int low,int high)
{
if(low<high)
{
int mid=(low+high)/2;
mergesort(low,mid);
mergesort(mid+1,high);
merge(low,mid,high);
}
}
void main()
{
int n,i,j;
clrscr();
printf("\nEnter how many no you want to enter:=");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("A[%d]:=",i+1);
scanf("%d",&ar[i]);
}
clrscr();
printf("\nBefore sorting:=\n");
for(j=0;j<n;j++)
{
printf("%d,",ar[j]);
}
mergesort(0,n-1);
printf("\nAfter sorting:=\n");
for(j=0;j<n;j++)
{
printf("%d,",ar[j]);
}
getch();
}

Source Code  :=https://github.com/shouvik126/merge-sort                 

Output :=

                             

Checking of loop in a LINKED LIST

Checking of LOOP in a LINKED LIST

There are many approaches to solve this type of problem. One easiest way is to use the traditional concept like, first create an array, while traversing the list for checking loop then add each new node address on that array, and while adding we have to check every time if there is any duplicate address previously present or not if present there is loop otherwise no loop.

On this concept time complexity as well as space complexity both are large. Space complexity is large because here we are using one extra array for storing address, and time complexity because while adding an address every we have to traverse the whole array. For this time complexity isO(n2).

The second approach which I have used over here is a concept of physics. We all know that in a circular path if there is two object running in two different speed then there will be an instance when faster object will cross slower object. Here also we have used same concept ,here we take two node type pointer one is slow another one is fast. while traversing every time slow will increase by one node whereas fast will increase by two nodes and there will be an instance when both the pointer will meet if there is a loop ,if there is no loop then there will be a time when both the pointer will reach at the end of the list means NULL value

  

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

struct node    //structure of node

{

int data;          //data

struct node *next; //pointer of next node

};

struct node *head;

void main()

{

int i,flag=0;

struct node *temp;

struct node *temp1;

struct node *slow,*fast;//pointer for checking loop in a linked list

clrscr();

head = NULL;

for(i=0;i<10;i++) //cre4ating 10 node inserting at head

{

temp=(struct node *)malloc(sizeof(struct node));

temp->data=i+1;   //storing data

temp->next=head;  //pointing to the head node

head= temp;       //current node become head

}

temp1=head;

printf("befor loop :=");

while(temp1!=NULL)  //printing of all the node

{

printf("%d -> %d,\n",temp1->data,temp1->next->data);

temp1=temp1->next;

}

temp=head;

for(i=1;i<=5;i++) //externally creating a loop from node 5 to node 3

{

if(i==3)

{

temp1=temp;//while traversing storing the address of node 3

}

if(i==5)

{

temp->next=temp1;//copying address of node 3 in next pointer of node 5

}

temp=temp->next;

}

slow=head;//at start both the node are pointing to head

fast=head;

while(1)

{

slow=slow->next;//every time slow is increased by 1 node

fast=fast->next->next; //and fast is increased by 2 node

if(slow==fast) //true if there is loop

{

flag=1; //if there is a loop there will be an instance

//when slow anf fast object meet each other(crossing point)

break;

}

if(slow==NULL || fast==NULL)//if there is no loop then there will

    //be a time when both the node will reach

    //at the end of the list

{

flag=0;

break;

}

}

if(flag==1)

{

printf("\nThere is loop");

}

else

{

printf("\nThere is no loop");

}

getch();

}

Source Code: =https://github.com/shouvik126/example1

OUTPUT: =

HackerRank Ice Cream Parlor problem

Ice Cream Parlor Problem

Problem link : https://www.hackerrank.com/challenges/icecream-parlor/problem

code : 

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// Complete the icecreamParlor function below.

vector<int> icecreamParlor(int m, vector<int> arr) {

    vector<int> result(2);

    int flag=0;

    for(int i=0;i<arr.size();i++)

    {

        //if(arr[i]<m)

        {

            flag=0;

            result[0]=i+1;

            for(int j=i+1;j<arr.size();j++)

            {

                if(i!=j)

                {

                    if((arr[i]+arr[j])==m)

                    {

                        flag=1;

                        result[1]=j+1;

                        break;

                    }

                }

            }

            if(flag==1)

                break;

        }//if end

    }//

    return result;

}

int main()

{

    ofstream fout(getenv("OUTPUT_PATH"));

    int t;

    cin >> t;

    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    for (int t_itr = 0; t_itr < t; t_itr++) {

        int m;

        cin >> m;

        cin.ignore(numeric_limits<streamsize>::max(), '\n');

        int n;

        cin >> n;

        cin.ignore(numeric_limits<streamsize>::max(), '\n');

        string arr_temp_temp;

        getline(cin, arr_temp_temp);

        vector<string> arr_temp = split_string(arr_temp_temp);

        vector<int> arr(n);

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

            int arr_item = stoi(arr_temp[i]);

            arr[i] = arr_item;

        }

        vector<int> result = icecreamParlor(m, arr);

        for (int i = 0; i < result.size(); i++) {

            fout << result[i];

            if (i != result.size() - 1) {

                fout << " ";

            }

        }

        fout << "\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;

}

Screenshot :

Binary Search using C

Binary Search

Binary search is a searching technique in a given sorted(ascending or descending) collection of the elements. We all know that there are two types of searching Linear Search, Binary Search, where Linear Search time complexity depends on the no of the element present in the collections I's Time complexity is O(n), whereas Binary Search depends on the height of the tree that is why Time complexity is O(log n). Binary search can be implemented by divide and conquer approach

Divide and Conquer: =It is an approach to solve the bigger problem. If a problem P(big) is given of size=n, which can not be solved at a time then it can be broken into Pk subproblem and obtain a solution for each of them then after combining  all those solutions we can get solutions of the main problem

Binary Search using Iteration
//binary search using iteration
#include<stdio.h>
#include<conio.h>
int ar[20];
int bsearch(int ,int);//prototype declaration
void main()
{
int flag,n,i,key;
clrscr();
printf("Enter no of element :=");
scanf("%d",&n);
//taking input from user
//input must be in sorted order
printf("\nEnter elements in sorted order\n");
for(i=0;i<n;i++)
{
printf("\nEnter Ar[%d]:=",i);
scanf("%d",&ar[i]);
}
printf("\nEnter the key u want to search:=");
scanf("%d",&key);
flag=bsearch(n,key);
if(flag==0)
{
printf("\nKey not found!!");
}
else
{
printf("\nKey %d found at [%d] position",key,flag+1);
}
getch();
}

//function defination start

int bsearch(int n,int key)
{
int mid,low=0,high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(ar[mid]==key)
{
return mid;//if element found at mid position return mid
}
else if(key<ar[mid])
{
high=mid-1;//if element is less then mid then upper is shifted to (mid-1)
}
else
{
low=mid+1;//if element is less then mid then upper is shifted to (mid-1)
}
}
return 0;

}

Source code : https://github.com/shouvik126/binary_search-iteration-

Output :

Binary Search using recursion : 

//Binary search using recursion

#include<stdio.h>

#include<conio.h>

int ar[30];

int bsearch(int ,int ,int);//prototype declaration

void main()

{

int low,high,n,i,key,flag;

clrscr();

printf("\nEnter no of element:=");

scanf("%d",&n);

printf("\nEnter elements in sorted order\n");

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

{

printf("\nEnter Ar[%d] :=",i);

scanf("%d",&ar[i]);

}

printf("\nEnter the key u want to search:=");

scanf("%d",&key);

low=0;

high=n-1;

flag=bsearch(low,high,key);//function called

if(flag==0)

{

printf("\nKey not found!!!");

}

else

{

printf("\nKey %d found at [%d] position@@",key,flag+1);

}

getch();

}

//function defination start

int bsearch(int low,int high,int key)

{

int mid;

if(low==high)

{

if(ar[low]==key)

{

return low;//one element exist with in range

}

else

return 0;

}

else

{

mid=(low+high)/2;

if(key==ar[mid])

return mid; //if element found at middle of the array

else if(key<ar[mid])

return bsearch(low,mid-1,key);//if searching key is less then ar[mid]

else

return bsearch(mid+1,high,key);//if searching key is greater then ar[mid]

}

}

Source Code : https://github.com/shouvik126/binary_search_recursion

Output :