-
Today...we should see an interesting application of hashing technique....
The Question is Quite simple and required basic programming skills.....




One Way Road


There are 4 Trucks A,B,C and D.
But the road is of only one way and we are interested for the departure of the truck and not the arrival.
Truck A will depart on every p,2p,3p day and so on.
Truck B will depart on every q day ,Truck C will depart on every r day and truck D will depart on every s day.
Find maximum number of Trucks that can be depart in the period of N days.
Note No more than 1 truck can depart in single day

Examples:The first input is number of total days followed by p,q,r,s
Input :10 2 3 4 5 
Output :4


//on day 2 Truck A can depart,on day 3 and 9 Truck B can depart.
Truck C cannot depart and Truck D can depart on day 5.


Input :10 2 2 4 4
Output :0


//Since moret than 1 truck is having same pattern of departure

Approach
We can apply the concept of hashing in this question.We know that the count will only increase if and only if there is only 1 Truck depart on particular day.
So we will maintain an array arr which will hold the records of the Truck which have already departed on a particular day.If after all the Trucks i.e A,B,C and D have departed in total N days then if the count is still 1 in that index then it is valid.
Else we will discard that day.

#include<bits/stdc++.h>
using namespace std;
int Check_Truck(int N,int p,int q,int r,int s)
{     //make an array of size N to store the take off day
      int arr[N+1];
      int count=0;    //To store the total number of days.
      //Initialize every element of the array with 0
      memset(arr,0,sizeof(arr));
       
      //check for the Truck A i.e on p day
       for(int i=p;i<=N;i=i+p)
       arr[i]=arr[i] + 1;           //If there are trucks which depart on these day then increment the value.
        
      //check for the Truck B i.e on q day
       for(int i=q;i<=N;i=i+q)
       arr[i]=arr[i] + 1;          //If there are trucks which depart on these day then increment the value.
        
      //check for the Truck C i.e on r day
       for(int i=r;i<=N;i=i+r)
       arr[i]=arr[i] + 1;           //If there are trucks which depart on these day then increment the value.
     
       //check for the Truck D i.e on s day
       for(int i=s;i<=N;i=i+s)
       arr[i]=arr[i] + 1;           //If there are trucks which depart on these day then increment the value.
       //finally check for the answer
       for(int i=1;i<=N;i++)
       {
          if(arr[i]==1)
          count++;
       }
    return count;
}
//Driver program
int main()
{
    int N,p,q,r,s;
    N=10,p=2,q=3,r=4,s=5;
    int answer=Check_Truck(N,p,q,r,s);
    cout<<answer;
  return 0;
}




Time Complexity :O(n)

Kindly follow the Blog for more such updates...
If you find anything wrong kindly mention that in the comments or email us....










Comments

Post a Comment

Popular posts from this blog

-
Image
Sphenic Number A  Sphenic Number  is a positive integer  n  which is product of exactly three distinct primes. The first few sphenic numbers are 30, 42, 66, 70, 78, 102, 105, 110, 114, … Sphenic number can be checked by fact that every sphenic number will have exactly 8 divisor  SPHENIC NUMBER So first We will try to find if the number is having exactly 8 divisors if not then simply answer is no.If there are exactly 8 divisors then we will confirm weather the first 3 digits after 1 are prime or not. Eg. 30 (sphenic number) 30=p*q*r(i.e p,q and r are three distinct prime no and their product are 30) the set of divisor is (1,2,3,5,6,10,15,30) Examples: 30 = 2 × 3 × 5 Sphenic number can be checked by fact that every sphenic number will have exactly 8 divisor  SPHENIC NUMBER So first We will try to find if the number is having exactly 8 divisors if not then simply answer is no.If there are exactly 8 divisors then we will confirm weather...
Read more

Fibonacci numbers with help of DP

-
Image
Well...the most and simple program which every programmer may have solved at least once.... Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….. In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation.... with base condition f(0)=0  f(1)=1 In general: f(n)=f(n-1) +f(n-2) Basic Approach: A simple method that is a direct recursive implementation mathematical recurrence relation given above Here is simple CPP program.... #include<bits/stdc++.h> using namespace std;     int fib( int n) {      if (n <= 1)          return n;      return fib(n-1) + fib(n-2); }     int main () {      int n = 9;      cout << fib(n);      return 0; } That was simple....isn't it........
Read more
-
Image
Tutorial-2 is out!!!!! Fasten your seat-belt! Problem-2:- Understanding this problem and its solution properly will make a strong foundation for you in the DP world .(This worked for me :-) ) Here we go- Given an array of integers(positive as well as negative) ,select some elements from this array(select a subset) such that:- Sum of those elements is maximum(Sum of the subset is maximum) . No 2 elements in the subset should be consecutive. Example :- {2,4,6,7,8} Answer:- {2+6+8=16} Common Trick : We create a dp-array , and dp[i] means the maximum sum we could get till index-’i’ of the array. For the above example, dp[1] = 2 (2), [This is the best answer you could get if size of the array was one] dp[2]= 4(4),[This is the best answer you could get if size of the array was two] dp[3]=8(6+2),[This is the best answer you could get if size of the array was three]………lets call this equation-(1)… dp[4]=11(7+4),[This is the best answer you could get if size of ...
Read more