Part-5 , (Coin Change)

 Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change?       



                                                  Dynamic Programming Solutions of
                                                        these kinds of solution

int count( int S[], int m, int n )

{

    // table[i] will be storing the number of solutions for

    // value i. We need n+1 rows as the table is consturcted

    // in bottom up manner using the base case (n = 0)

    int table[n+1];

 

    // Initialize all table values as 0

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

 

    // Base case (If given value is 0)

    table[0] = 1;

 

    // Pick all coins one by one and update the table[] values

    // after the index greater than or equal to the value of the

    // picked coin

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

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

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

 

    return table[n];

}

 

int main()

{

    int arr[] = {1, 2, 3};

    int m = sizeof(arr)/sizeof(arr[0]);

    int n = 4;

    printf(" %d ", count(arr, m, n));

    return 0;

}

 

 

           Problem : https://practice.geeksforgeeks.org/problems/coin-change/0

 

 

 

#include<bits/stdc++.h>

// Nayeem Shahriar Joy , Applied Physics & Electronic Engineering , University of Rajshahi.

using namespace std;

int count( int S[], int m, int n )
{
    int dp[n+1];

    memset(dp, 0, sizeof(dp));

    dp[0] = 1;

    for(int i=0; i<m; i++){
        for(int j=S[i]; j<=n; j++){
            dp[j] += dp[j-S[i]];
        }
    }

    return dp[n];
}

int main()

{
    int t,s,x,N;
    cin>>t;
    while(t--)
    {
        cin>>s;
        int A[s];
        for(int i=0;i<s;i++)
        {
            cin>>A[i];
        }
        cin>>N;
        cout<<count(A,s,N)<<endl;
    }
    return 0;

}
 

 

                 

 

Part-4,Min Cost Path

From (0,0)  to  (R,R)

                                                      Use Of Dynamic Programming 
                                                      TIME  COMPLEXITY  O(m*n)  


#include<bits/stdc++.h>

using namespace std;

int minCost(int cost[R][C], int m, int n)
{
     int i, j;
     int dp[R][C]; 

     dp[0][0] = cost[0][0];

     /* Initialize first column of total cost(tc) array */
     for (i = 1; i <= m; i++)
        dp[i][0] = dp[i-1][0] + cost[i][0];

     /* Initialize first row of tc array */
     for (j = 1; j <= n; j++)
        dp[0][j] = dp[0][j-1] + cost[0][j];

     /* Construct rest of the tc array */
     for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++)
            dp[i][j] = min(dp[i-1][j-1],
                           dp[i-1][j],
                           dp[i][j-1]) + cost[i][j];

     return dp[m][n];
}

int main()
{
   int cost[R][C] = { {1, 2, 3},
                      {4, 8, 2},
                      {1, 5, 3} };
   printf(" %d ", minCost(cost, 2, 2));
   return 0;
}

Part-3,Largest Sum Contiguous Subarray

       Largest Sum Contiguous Subarray

 

                                                  Use of Dynamic Programming 
                                                  TIME  COMPLEXITY  O(n)                          

#include<bits/stdc++.h>

using namespace std;



int maxSubArraySum(int a[], int size)
{
   int max_so_far = a[0];
   int curr_max = a[0];

   for (int i = 1; i < size; i++)
   {
        curr_max = max(a[i], curr_max+a[i]);
        max_so_far = max(max_so_far, curr_max);
   }
   return max_so_far;
}



int main()

{

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

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

   int max_sum = maxSubArraySum(a, n);

   cout << "Maximum contiguous sum is " << max_sum;

   return 0;

}

 

 

                      A Problem & It's Solution 

 

http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/      




#include<bits/stdc++.h>

using namespace std;

// Nayeem Shahriar Joy , Applied physics & Electronic Engineering , University of Rajshahi.

int maxSubArraySum(int a[], int size)
{
   int max_so_far = a[0];
   int curr_max = a[0];

   for (int i = 1; i < size; i++)
   {
        curr_max = max(a[i], curr_max+a[i]);
        max_so_far = max(max_so_far, curr_max);
   }
   return max_so_far;
}

/* Driver program to test maxSubArraySum */
int main()
{
    int t;
    cin>>t;
    while(t--){
        int x;
        cin>>x;
        int a[x];
        for(int i=0;i<x;i++)
        {
            cin>>a[i];
        }
   int n = sizeof(a)/sizeof(a[0]);
   int max_sum = maxSubArraySum(a, n);
   cout<< max_sum<<endl;
    }
   return 0;
}


 

 

Part-2 , Find nCr ( BinomialCoefficient ) for given n and r

                                     Find nCr for given n and r


                                                  Use Recursive Formula ,
                                               
#include<bits/stdc++.h>

using namespace std;

int BinomialCoefficient(int n,int k)

{
    if(k==0||k==n)
        return 1;

    return BinomialCoefficient(n-1,k-1)+BinomialCoefficient(n-1,k);
}

int main()

{
    int n,k;
    cin>>n>>k;
    cout<<BinomialCoefficient(n,k)<<endl;
    return 0;
}

                                                            Use Of Dynamic Programming

                                                            Time Complexity  O(n*k)

  


#include<bits/stdc++.h>

using namespace std;

int BinomialCoefficient(int n,int k)

{
   int dp[n+1][k+1];
   int i,j;
   for(int i=0;i<=n;i++)
   {
       for(int j=0;j<=min(i,k);j++)
       {
           if(j==0||j==i)
            dp[i][j]=1;
           else
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
       }
   }
   return dp[n][k];
}

int main()

{
    int n,k;
    cin>>n>>k;
    cout<<BinomialCoefficient(n,k)<<endl;
    return 0;
}


                                            A    Problem  & It's Solution 

https://practice.geeksforgeeks.org/problems/ncr/0 


#include<bits/stdc++.h>

using namespace std;

// Nayeem Shahriar Joy , Applied Physics & Electronic Engineering,University of Rajshahi.

int BinomialCoefficient(int n,int k)

{
   int dp[n+1][k+1];
   int i,j;
   for(int i=0;i<=n;i++)
   {
       for(int j=0;j<=min(i,k);j++)
       {
           if(j==0||j==i)
            dp[i][j]=1;
           else
            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%1000000007;
       }
   }
   return dp[n][k];
}

int main()

{
    int t;
    cin>>t;
    while(t--){
    int n,k;
    cin>>n>>k;
    if(n<k)
    {
        cout<<"0"<<endl;
    }
    else{
    cout<<BinomialCoefficient(n,k)<<endl;
    }
    }
    return 0;
}

Part-1 , Fibonacchi Number Finding

Tricks For Fibonacchi ,

If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)

                                                 TIME COMPLEXITY ( O Log ( n ) )


#include<bits/stdc++.h>

using namespace std;

const int MAX =1000;
int fibonacchi[1000]={0};


int fib(int n)
{
    int k;
    if(n==0)
    {

        return 0;
    }
    if(n==1||n==2)
    {
        return (fibonacchi[n]=1);
    }
    if(fibonacchi[n])
        return fibonacchi[n];

    k=(n&1)? (n+1)/2: n/2;

    fibonacchi[n]=(n&1)? (fib(k)*fib(k)+(fib(k-1)*fib(k-1))) : (2*fib(k-1)+fib(k))*fib(k);

    return fibonacchi[n];
}

int main()

{
    int x;
    cin>>x;
    cout<<fib(x)<<endl;
    return 0;
}


                                                          Use Of Dynamic Programming

                                                          TIME COMPLEXITY O(N);   


#include<bits/stdc++.h>

using namespace std;

int fib(int n)
{
  /* Declare an array to store Fibonacci numbers. */
  int f[n+1];
  int i;

  /* 0th and 1st number of the series are 0 and 1*/
  f[0] = 0;
  f[1] = 1;

  for (i = 2; i <= n; i++)
  {
      /* Add the previous 2 numbers in the series
         and store it */
      f[i] = f[i-1] + f[i-2];
  }

  return f[n];
}

int main ()
{
  int n;
  cin>>n;
  cout<<fib(n)<<endl;
  return 0;
}
 

                                                    A Problem & It's Solution 

 https://practice.geeksforgeeks.org/problems/nth-fibonacci-number/0


#include<bits/stdc++.h>

using namespace std;

// Nayeem Shahriar Joy , Applied Physics & Electronic Engineering , UNiversity of Rajshahi.

const int MAX =1000;
long dp[1000]={0};


int fib(int n)
{
   dp[0]=0;
   dp[1]=1;
   for(int i=2;i<=1000;i++)
   {
       dp[i]=(dp[i-1]+dp[i-2])%1000000007;

   }
   return dp[n];
}
int main() {
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cout<<fib(n)<<endl;

    }

    return 0;
}

Aaah! Kattis Problem Solution In Java

// Nayeem Shahriar Joy , Applied Physics & Electronic Engineering , University of Rajshahi.

import java.util.Scanner;

public class Joy {

public static void main(String[] args) {

String s1,s2;

Scanner sc1=new Scanner(System.in);

s1=sc1.nextLine();

s2=sc1.nextLine();

int able=s1.length();

int say=s2.length();

if(able>=say)

{

System.out.print("go");

}

else

{

System.out.print("no");

}

}

}

Seven Wonders Kattis Problem Solution In Java

//Nayeem Shahriar Joy,Applied Physics & Electronic Engineering, University of Rajshahi.

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

public class Joy{

public static void main(String[] args) {

Scanner io = new Scanner(System.in);

String s=io.nextLine();

long ans=0;

int C=0,T=0,G=0;

for(int i=0;i<s.length();i++)

{

char c=s.charAt(i);

if(c=='T')

{

T++;

}

else if(c=='G')

{

G++;

}

else if(c=='C')

{

C++;

}

}

int seven=Math.min(T, Math.min(C,G));

ans=(T*T)+(C*C)+(G*G)+(seven*7);

System.out.println(ans);

}

}

Apaxiaaaaaaaaaaaans! Kattis Problem Solution In Java

//Nayeem Shahriar Joy,Applied Physics & Electronic Engineering, University of Rajshahi.
 

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

import javax.swing.text.html.HTMLDocument.Iterator;

public class Joy{

public static void main(String[] args) {

Scanner io = new Scanner(System.in);

String s=io.nextLine();

int i;

for( i=0;i<s.length()-1;i++)

{

if(s.charAt(i)!=s.charAt(i+1))

{

System.out.print(s.charAt(i));

}

}

System.out.print(s.charAt(i));

System.out.println();

}

}

Cryptographer's Conundrum Kattis Problem Solution In Java

//Nayeem Shahriar Joy,Applied Physics & Electronic Engineering, University of Rajshahi.
 

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

import javax.swing.text.html.HTMLDocument.Iterator; 

 

public class Joy{

public static void main(String[] args) {

Scanner io = new Scanner(System.in);

String s=io.nextLine();

int count=0;

for(int i=0;i<s.length();i++) {

if(!((i%3==0&&s.charAt(i)=='P')||(i%3==1&&s.charAt(i)=='E')||(i%3==2&&s.charAt(i)=='R')))

{

count++;

}

}

System.out.println(count);

}

}

Speed Limit Kattis Problem Solution In Java

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

import javax.swing.text.html.HTMLDocument.Iterator;

public class Joy{

public static void main(String[] args) {

// Get input from the user w/ sentinel logic

Scanner reader = new Scanner(System.in);

int pairs = Integer.parseInt(reader.nextLine());

// Keep track of distances

ArrayList<Integer> distances = new ArrayList<Integer>();

while(pairs != -1){ // While still accepting input

int distance = 0;

int hours = 0;

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

String[] temp = reader.nextLine().split(" "); // Put input into a string

distance += Integer.parseInt(temp[0]) * (Integer.parseInt(temp[1]) - hours); // distance is mph times new hours - old hours

hours = Integer.parseInt(temp[1]); // keep track of current hours

}

distances.add(distance);

pairs = Integer.parseInt(reader.nextLine());

} // end while loop

// Output data to the user

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

System.out.println(distances.get(i) + " miles");

}

// Closed the reader

reader.close();

}// end main

}

Pet Kattis Problem Solution In Java

//Nayeem Shahriar Joy,Applied Physics & Electronic Engineering, University of Rajshahi.

 

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

import javax.swing.text.html.HTMLDocument.Iterator; 

 

public class Joy{

public static void main(String[] args) {

// Get input from the user w/ sentinel logic

Scanner io = new Scanner(System.in);

int index=0;

int sum=0,sum1 = 0;

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

{

int a=io.nextInt();

int b=io.nextInt();

int c=io.nextInt();

int d=io.nextInt();

sum=a+b+c+d;

if(sum1<=sum)

{

sum1=sum;

index=i;

}

}

System.out.println(index+" "+sum1);

}

}

Modulo Kattis Problem Solution In Java

//Nayeem Shahriar Joy,Applied Physics & Electronic Engineering, University of Rajshahi.
 

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set; 

 

public class Joy{

public static void main(String[] args) {

// Get input from the user w/ sentinel logic

Scanner io = new Scanner(System.in);

Set<Integer>s=new HashSet<Integer>();

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

{

int a=io.nextInt();

s.add(a%42);

}

System.out.println(s.size());

}

}

A Real Challenge Kattis Problem Solution In Java

//Nayeem Shahriar Joy,Applied Physics & Electronic Engineering, University of Rajshahi.

 

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set; 

public class Joy{

public static void main(String[] args) {

// Get input from the user w/ sentinel logic

Scanner io = new Scanner(System.in);

double a = io.nextDouble();

System.out.println(4*Math.sqrt(a));

}

}

Mixed Fractions Kattis Problem Solution In Java

//Nayeem Shahriar Joy,Applied Physics & Electronic Engineering, University of Rajshahi.
 

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set; 

 

public class Joy{

public static void main(String[] args) {

// Get input from the user w/ sentinel logic

Scanner in = new Scanner(System.in);

String s=in.nextLine();

String[]values=s.split(" ");

int a=Integer.parseInt(values[0]);

int b=Integer.parseInt(values[1]);

ArrayList<String>answers=new ArrayList<String>();

while(!(s.trim().equals("0 0")))

{

String[] mixedFunction=s.split(" ");

int A=Integer.parseInt(mixedFunction[0]);

int B=Integer.parseInt(mixedFunction[1]);

int frac=A/B;

int num=A%B;

answers.add(""+frac+" "+num+" / "+B);

s=in.nextLine();

}

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

{

System.out.println(answers.get(i));

}

}

}

One Chicken Per Person! Kattis Problem Solution In Java

//Nayeem Shahriar Joy,Applied Physics & Electronic Engineering, University of Rajshahi.

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

public class Joy{

public static void main(String[] args) {

// Get input from the user w/ sentinel logic

Scanner in = new Scanner(System.in);

String s=in.nextLine();

String[]values=s.split(" ");

int a=Integer.parseInt(values[0]);

int b=Integer.parseInt(values[1]);

if(a<b&&(b-a)!=1)

{

System.out.println("Dr. Chaz will have "+(b-a)+" pieces of chicken left over!");

}

else if(a<b&&(b-a)==1)

{

System.out.println("Dr. Chaz will have "+(b-a)+" piece of chicken left over!");

}

else if(a>b&&(a-b)!=1)

{

System.out.println("Dr. Chaz needs "+(a-b)+" more pieces of chicken!");

}

else if(a>b&&(a-b)==1)

{

System.out.println("Dr. Chaz needs "+(a-b)+" more piece of chicken!");

}

}

}

Line Them Up Kattis Problem Solution In Java

//Nayeem Shahriar Joy,Applied Physics & Electronic Engineering, University of Rajshahi.
 

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set; 

 

public class Joy{

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int a=Integer.parseInt(in.nextLine());

ArrayList<String>s1=new ArrayList<String>();

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

{

String s=in.nextLine();

s1.add(s);

}

boolean decreasing=false;

boolean increasing=false;

for(int j=0;j<s1.size()-1;j++)

{

if(s1.get(j).compareTo(s1.get(j+1))<0)

{

decreasing=true;

}

else

{

increasing=true;

}

}

if(increasing&&decreasing)

{

System.out.println("NEITHER");

}

else if(!increasing)

{

System.out.println("INCREASING");

}

else

{

System.out.println("DECREASING");

}

}

}