Code Engineer

/* N = 100 Factor Power   2      2   5      2 N = 35 Factor  Power   5      1   7      1     nput: 2 100 35 Output: 2 2 5 2 5 1 7 1 we can see it as key value printing we can use map */ #include <bits/stdc++.h> using namespace std; void primeFactors(int n) { map<int,int> m; while(n%2==0) // runs two times for 100 making it 25, covered divisible by 4 { m[2]++; n=n/2; } for(int i=3;i<=n;i=i+2) // checking for all odd numbers note if 3 checked then it wont check for 9 only primes { while(n%i==0) { m[i]++; n=n/i; } } map<int,int> ::iterator itr; for(itr=m.begin();itr!=m.end();itr++) { cout<<itr->first<<" "<<itr->second<<" "; } cout<<endl; } int main() { int n,i,t; cin >> t; while(t--){     cin >> n;     primeFactors(n); } return 0; }

Examples: LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3. LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4. #include<bits/stdc++.h>   int max(int a, int b);   int lcs( char *X, char *Y, int m, int n ) {    int L[m+1][n+1];    int i, j;  for (i=0; i<=m; i++)    {      for (j=0; j<=n; j++)      {        if (i == 0 || j == 0)          L[i][j] = 0;          else if (X[i-1] == Y[j-1])          L[i][j] = L[i-1][j-1] + 1;          else          L[i][j] = max(L[i-1][j], L[i][j-1]);      }    }       //L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1]    return L[m][n]; }   // Utility function to get max of 2 integers int max(int a, int b) {     return (a > b)? a : b; }   /* Driver program to test above function int main() {   char X[] = "AGGTAB";   char Y[] = "GXTXAYB";     int m = strlen(X);   int n = strlen(Y);     printf("Length of LCS is %d", lcs( X, Y,

Count all possible paths from top left to bottom right The task is to count all the possible paths from top left to bottom right of a mXn matrix with the constraints that from each cell you can either move only to right or down. Input:  First line consists of T test cases. First line of every test case consists of N and M, denoting the number of rows and number of column respectively. Output:  Single line output i.e count of all the possible paths from top left to bottom right of a mXn matrix. Since output can be very large number use %10^9+7. Constraints: 1<=T<=100 1<=N<=100 1<=M<=100 Example: Input: 1 3 3 Output: 6 #include <iostream> using namespace std; int path(int m , int n) { int a[m][n]; // now we want to find the total paths from left top to bottom right //we use the concept of longest common subsequence to do it //in l.c.s we check if a[i]==a[j] // if true then done add 1 to diagnol element else copy max(left,to

// A Dynamic Programming based solution that uses  // table C[][] to calculate the Binomial Coefficient #include<bits/stdc++.h> using namespace std;   // Prototype of a utility function that // returns minimum of two integers int min(int a, int b);   // Returns value of Binomial Coefficient C(n, k) int binomialCoeff(int n, int k) {     int C[n + 1][k + 1];     int i, j;       // Caculate value of Binomial Coefficient     // in bottom up manner     for (i = 0; i <= n; i++)     {         for (j = 0; j <= min(i, k); j++)         {             // Base Cases             if (j == 0 || j == i)                 C[i][j] = 1;               // Calculate value using previously             // stored values             else                 C[i][j] = C[i - 1][j - 1] +                           C[i - 1][j];                           // ncr formula-> (n)c(r)= (n-1)c(r)+(n-1)c(r-1) if r=0,r=n then ncr=1         }     }       return C[n][k]; }   // A u

// sieve of Atkin is a popular way to find all the prime numbers in range using the dp approach and is //better than the erronthesis approach // C++ program for implementation of Sieve of Atkin #include <bits/stdc++.h> using namespace std;   int SieveOfAtkin(int limit) {     // 2 and 3 are known to be prime     if (limit > 2)         cout << 2 << " ";     if (limit > 3)         cout << 3 << " ";       // Initialise the sieve array with false values     bool sieve[limit];     for (int i = 0; i < limit; i++)         sieve[i] = false;     for (int x = 1; x * x < limit; x++) {         for (int y = 1; y * y < limit; y++) {                           // Main part of Sieve of Atkin             int n = (4 * x * x) + (y * y);             if (n <= limit && (n % 12 == 1 || n % 12 == 5))                 sieve[n] ^= true;               n = (3 * x * x) + (y * y);             if (n <= limit &

/* Given two integers L and R find the difference of number of composites and primes between the range L and R (both inclusive). Input: First line of input contains of an integer 'T' denoting number of test cases . Then T test cases follow. Each test contains two integers L and R . Output: For each case print an integer corresponding to the answer . Constraints: 1<=T<=100 1<=L<=R<=10^7 Example: Input: 2 4 4 4 6 Output: 1 1 */ // given l , r print no of comp- no of prime  T.C->0.21 // normal approac i*i<=n gives TLE > 3.14 #include<bits/stdc++.h> using namespace std; bool prime[100001]; void SieveOfEratosthenes() {     memset(prime, true, sizeof(prime));     prime[0]=false;     prime[1]=false;     for (int p=2; p*p<=10000000; p++)     {             if (prime[p] == true) // we make all multiples of prime false         {             for (int i=p*p; i<=10000000; i += p)  // we make all multiples of prime f

/* Given an array of n integers where each value represents number of chocolates in a packet. Each packet can have variable number of chocolates. There are m students, the task is to distribute chocolate packets such that: Each student gets one packet. The difference between the number of chocolates in packet with maximum chocolates and packet with minimum chocolates given to the students is minimum. Examples: Input :  arr[] = {7, 3, 2, 4, 9, 12, 56} m = 3 Output:  Minimum Difference is 2 We have seven packets of chocolates and we need to pick three packets for 3 students If we pick 2, 3 and 4, we get the minimum difference between maximum and minimum packet sizes. Input :  arr[] = {3, 4, 1, 9, 56, 7, 9, 12} m = 5 Output:  Minimum Difference is 6 The set goes like 3,4,7,9,9 and the output is 9-3 = 6 Input :  arr[] = {12, 4, 7, 9, 2, 23, 25, 41, 30, 40, 28, 42, 30, 44, 48, 43, 50} m = 7 Output:  Minimum Difference is 10 We need to pick 7 packets. We pick 40, 41, 42, 44,

Hello guys.. Here you can find all the important programming questions that i have solved.., if you get any doubt feel free to ask below in comment section :)