Q1 Find trailing zeroes?

Ans [Link]

n = 5: There is one 5 and 3 2s in prime factors of 5! (2 * 2 * 2 * 3 * 5). So count

of trailing 0s is 1.

n = 11: There are two 5s and three 2s in prime factors of 11! (2 8 * 34 * 52 * 7).
So count of trailing 0s is 2.

We can easily observe that the number of 2s in prime factors is always more than or
equal to the number of 5s. So if we count 5s in prime factors, we are done. How to
count total number of 5s in prime factors of n!? A simple way is to calculate
floor(n/5). For example, 7! has one 5, 10! has two 5s. It is done yet, there is one
more thing to consider. Numbers like 25, 125, etc have more than one 5. For example
if we consider 28!, we get one extra 5 and number of 0s become 6. Handling this is
simple, first divide n by 5 and remove all single 5s, then divide by 25 to remove
extra 5s and so on. Following is the summarized formula for counting trailing 0s.

Trailing 0s in n! = Count of 5s in prime factors of n!

= floor(n/5) + floor(n/25) + floor(n/125) + ....

#include <iostream>
using namespace std;

int findTrailingZeros(int n)
{
// Initialize result
int count = 0;

// Keep dividing n by powers of

// 5 and update count
for (int i = 5; n / i >= 1; i *= 5)
count += n / i;

return count;
}
int main()
{
int n = 100;
cout << "Count of trailing 0s in " << 100
<< "! is " << findTrailingZeros(n);
return 0;
}

--------------------------------------------------

Q Codeforces Aggresive Cows

[Link]
questions-du1089cq6

int F(int x)
{
//We can always place the first cow in the leftmost stall
int cowsplaced=1,lastpos=pos[0];
 for(int i=1;i<N;i++)
{
if(pos[i]-lastpos>=x)
{
//We are at least x away from last placed cow
//So we can place one here
if(++cowsplaced==C)return 1;
lastpos=pos[i];
}
}
return 0;
}

sort(pos,pos+N);
//Invariant : F(start) is always 1, F(end) is always 0
int start=0,end=pos[N-1]-pos[0]+1,mid;
while(end-start>1)
{
mid=(end+start)>>1;
(F(mid)?start:end)=mid;
}
return start;

-------------------------------------------------------------

First negative integer in every window of size k

Given an array and a positive integer k, find the first negative integer for each
window(contiguous subarray) of size k. If a window does not contain a negative
integer, then print 0 for that window.

It is a variation of the problem of Sliding Window Maximum.

We create a Dequeue, Di of capacity k, that stores only useful elements of the
current window of k elements. An element is useful if it is in the current window
and it is a negative integer. We process all array elements one by one and maintain
Di to contain useful elements of current window and these useful elements are all
negative integers. For a particular window, if Di is not empty then the element at
front of the Di is the first negative integer for that window, else that window
does not contain a negative integer.

#include <bits/stdc++.h>

using namespace std;

void printFirstNegativeInteger(int arr[], int n, int k)

{
// A Double Ended Queue, Di that will store indexes of
// useful array elements for the current window of size k.
// The useful elements are all negative integers.
deque<int> Di;

/* Process first k (or first window) elements of array */

 int i;
for (i = 0; i < k; i++)
// Add current element at the rear of Di
// if it is a negative integer
if (arr[i] < 0)
Di.push_back(i);

// Process rest of the elements, i.e., from arr[k] to arr[n-1]

for ( ; i < n; i++)
{
// if Di is not empty then the element at the
// front of the queue is the first negative integer
// of the previous window
if (![Link]())
cout << arr[[Link]()] << " ";

// else the window does not have a

// negative integer
else
cout << "0" << " ";

// Remove the elements which are out of this window

while ( (![Link]()) && [Link]() < (i - k + 1))
Di.pop_front(); // Remove from front of queue

// Add current element at the rear of Di

// if it is a negative integer
if (arr[i] < 0)
Di.push_back(i);
}

// Print the first negative

// integer of last window
if (![Link]())
cout << arr[[Link]()] << " ";
else
cout << "0" << " ";

// Driver program to test above functions

int main()
{
int arr[] = {12, -1, -7, 8, -15, 30, 16, 28};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 3;
printFirstNegativeInteger(arr, n, k);
return 0;
}

----------------------------------------------------------

Minimum number of swaps to sort the array

[Link]

// C++ program to find minimum number of swaps

// required to sort an array
#include<bits/stdc++.h>

using namespace std;

// Function returns the minimum number of swaps

// required to sort the array
int minSwaps(int arr[], int n)
{
// Create an array of pairs where first
// element is array element and second element
// is position of first element
pair<int, int> arrPos[n];
for (int i = 0; i < n; i++)
{
arrPos[i].first = arr[i];
arrPos[i].second = i;
}

// Sort the array by array element values to

// get right position of every element as second
// element of pair.
sort(arrPos, arrPos + n);

// To keep track of visited elements. Initialize

// all elements as not visited or false.
vector<bool> vis(n, false);

// Initialize result
int ans = 0;

// Traverse array elements

for (int i = 0; i < n; i++)
{
// already swapped and corrected or
// already present at correct pos
if (vis[i] || arrPos[i].second == i)
continue;

// find out the number of node in

// this cycle and add in ans
int cycle_size = 0;
int j = i;
while (!vis[j])
{
vis[j] = 1;

// move to next node

j = arrPos[j].second;
cycle_size++;
}

// Update answer by adding current cycle.

if (cycle_size > 0)
{
ans += (cycle_size - 1);
}
}

// Return result
 return ans;
}

// Driver program to test the above function

int main()
{
int arr[] = {1, 5, 4, 3, 2};
int n = (sizeof(arr) / sizeof(int));
cout << minSwaps(arr, n);
return 0;
}

----------------------------------------------------------

Chef and Football Player Codechef April Lunchtime 2020

int main()
{
int t,n;
ll s,tmp;
vl::iterator x;
ll left,sum;
bool found;
int pos;
cin>>t;
while(t--)
{
cin>>n>>s;
found=false;
unordered_map<int,vl> store;
ll arr[n][2];
fo(i,n) cin>>arr[i][0];
fo(i,n)
{
cin>>arr[i][1];
if(arr[i][1]==0) store[0].push_back(arr[i][0]);
else store[1].push_back(arr[i][0]);
}
sort(store[0].begin(),store[0].end());
sort(store[1].begin(),store[1].end());
for(int ii=0;ii<n;++ii)
{
if(arr[ii][1]==1)
{
x=lower_bound(store[0].begin(),store[0].end(),arr[ii][0]);
if(x==store[0].end())
{
continue;
}
sum=*x+arr[ii][0]+s;
if(sum<=100)
{
found=true;
break;
}

}
 else
{
x=lower_bound(store[1].begin(),store[1].end(),arr[ii][0]);
if(x==store[1].end()) continue;
sum=*x+arr[ii][0]+s;
if(sum<=100)
{
found=true;
break;
}
}
}

if(found) cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
return 0;

-----------------------------------------------------------------------
Nearest One in matrix

#include<iostream>
#include<stdio.h>
#include<queue>
#include<utility>
using namespace std;
int isSafe(int x,int y,int n,int m)
{
if(x<0 || x>=m || y<0 || y>=n) return 0;
return 1;
}
int main()
{
int n,m;
queue<pair<int,int>> que;
cin>>n>>m;
int dist[n][m];

int mtx[n][m];
int row[]={0,1,0,-1};
int col[]={1,0,-1,0};
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
cin>>mtx[i][j];
if(mtx[i][j]==1)
{
[Link](make_pair(i,j));
dist[i][j]=0;
}
else dist[i][j]=-1;
}
}
 pair<int,int> p;
int x,y;
while(![Link]())
{
p=[Link]();
[Link]();
cout<<"popped:"<<[Link]<<" "<<[Link]<<endl;
for(int i=0;i<4;++i)
{
x=row[i];
y=col[i];
if(!isSafe([Link]+x,[Link]+y,n,m)) continue;
if(dist[[Link]+x][[Link]+y]==-1)
{
dist[[Link]+x][[Link]+y]=dist[[Link]][[Link]]+1;
[Link](make_pair([Link]+x,[Link]+y));
}
else
{
if(dist[[Link]+x][[Link]+y]>dist[[Link]][[Link]]+1)
dist[[Link]+x][[Link]+y]=dist[[Link]][[Link]]+1;
//printf("dist[%d][%d]:%d\n",[Link]+x,[Link]+y,dist[[Link]+x]
[[Link]+y]);
}

cout<<dist[0][0]<<endl;

return 0;
}

---------------------------------------------------------

Find the pivot point of rotated sorted array

--------------------------------------------------------------------
K-Partitions of the array such that the sum is equal

[Link]

#include <iostream>
#include <numeric>

// Function to check if all subsets are filled or not

bool checkSum(int sumLeft[], int k)
{
int r = true;
for (int i = 0; i < k; i++)
{
if (sumLeft[i] != 0)
r = false;
}

return r;
}

// Helper function for solving k partition problem

// It return true if there exists k subsets with given sum
bool subsetSum(int S[], int n, int sumLeft[], int A[], int k)
{
// return true if subset is found
if (checkSum(sumLeft, k))
return true;

// base case: no items left

if (n < 0)
return false;

bool res = false;

// consider current item S[n] and explore all possibilities

// using backtracking
for (int i = 0; i < k; i++)
{
if (!res && (sumLeft[i] - S[n]) >= 0)
{
// mark current element subset
A[n] = i + 1;

// add current item to i'th subset

sumLeft[i] = sumLeft[i] - S[n];

// recur for remaining items

res = subsetSum(S, n - 1, sumLeft, A, k);

// backtrack - remove current item from i'th subset

sumLeft[i] = sumLeft[i] + S[n];
}
}

// return true if we get solution

return res;
}

// Function for solving k-partition problem. It prints the subsets if

// set S[0..n-1] can be divided into k subsets with equal sum
void partition(int S[], int n, int k)
{
// base case
if (n < k)
{
std::cout << "k-Partition of set S is not Possible";
return;
}
 // get sum of all elements in the set
int sum = std::accumulate(S, S + n, 0);

int A[n], sumLeft[k];

// create an array of size k for each subset and initialize it

// by their expected sum i.e. sum/k
for (int i = 0; i < k; i++)
sumLeft[i] = sum/k;

// return true if sum is divisible by k and the set S can

// be divided into k subsets with equal sum
bool res = !(sum % k) && subsetSum(S, n - 1, sumLeft, A, k);

if (!res)
{
std::cout << "k-Partition of set S is not Possible";
return;
}

// print all k-partitions

for (int i = 0; i < k; i++)
{
std::cout << "Partition " << i << " is: ";
for (int j = 0; j < n; j++)
if (A[j] == i + 1)
std::cout << S[j] << " ";
std::cout << std::endl;
}
}

// main function for k-partition problem

int main()
{
// Input: set of integers
int S[] = { 7, 3, 5, 12, 2, 1, 5, 3, 8, 4, 6, 4 };

// number of items in S
int n = sizeof(S) / sizeof(S[0]);
int k = 5;

partition(S, n, k);

return 0;
}
--------------------------------------------------------------------

Rotate the SQUARE Matrix by 90 ANTI-CLOCKWISE

#include <bits/stdc++.h>
#define N 4
using namespace std;

// anti-clockwise direction by 90
void rotateMatrix(int mat[][N])
{
// Consider all squares one by one
for (int i = 0; i < N / 2; i++) {
 // Consider elements in group
// of 4 in current square
for (int j = i; j < N - i - 1; j++) {
// Store current cell in
// temp variable
int temp = mat[i][j];

// Move values from right to top

mat[i][j] = mat[j][N - 1 - i];

// Move values from bottom to right

mat[j][N - 1 - i]
= mat[N - 1 - i][N - 1 - j];

// Move values from left to bottom

mat[N - 1 - i][N - 1 - j]
= mat[N - 1 - j][i];

// Assign temp to left

mat[N - 1 - j][i] = temp;
}
}
}

-----------------------------------------------------------

Rotate Non Square Matrix clockwise

for (r = 0; r < m; r++)

{
for (c = 0; c < n; c++)
{
// Hint: Map each source element indices into
// indices of destination matrix element.
dest_buffer [ c ] [ m - r - 1 ] = source_buffer [ r ] [ c ];
}
}

--------------------------------------------------------------------

Diameter of Binary Tree

/* Max of following three

1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1 */

Diameter of Binary tree is

max(leftHeight+rightHeight+1,max(leftDiameter,rightDiameter))

int diameter(struct node * tree)

{
/* base case where tree is empty */
if (tree == NULL)
return 0;
 /* get the height of left and right sub-trees */
int lheight = height(tree->left);
int rheight = height(tree->right);

/* get the diameter of left and right sub-trees */

int ldiameter = diameter(tree->left);
int rdiameter = diameter(tree->right);

/* Return max of following three

1) Diameter of left subtree
2) Diameter of right subtree
3) Height of left subtree + height of right subtree + 1 */
return max(lheight + rheight + 1, max(ldiameter, rdiameter));
}

int height(struct node* node)

{
/* base case tree is empty */
if(node == NULL)
return 0;

/* If tree is not empty then height = 1 + max of left

height and right heights */
return 1 + max(height(node->left), height(node->right));
}

------------------------------------------------------------

Print nodes at each level in Binary Tree

1st approach

void printLevelOrder(node *root)

{
// Base Case
if (root == NULL) return;

// Create an empty queue for level order tarversal

queue<node *> q;

// Enqueue Root and initialize height

[Link](root);

while ([Link]() == false)

{
// nodeCount (queue size) indicates number
// of nodes at current lelvel.
int nodeCount = [Link]();
d
// Dequeue all nodes of current level and
// Enqueue all nodes of next level
while (nodeCount > 0)
{
node *node = [Link]();
cout << node->data << " ";
[Link]();
if (node->left != NULL)
 [Link](node->left);
if (node->right != NULL)
[Link](node->right);
nodeCount--;
}
cout << endl;
}
}

2nd approach

void printGivenLevel(struct node* root, int level)

{
if (root == NULL)
return;
if (level == 1)
printf("%d ", root->data);
else if (level > 1)
{
printGivenLevel(root->left, level-1);
printGivenLevel(root->right, level-1);
}
}

--------------------------------------------------------------------
Find a pair with given sum

[Link]

-----------------------------------------------------------------

Two pointer technique

[Link]

-----------------------------------------------------------------

DP Problems

Heap/Priority Queue

-----------------------------------------------------------------

Find kth Largest Element

1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given
array. O(k)
2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with
root of MH.
��a) If the element is greater than the root then make it root and call heapify for
MH
��b) Else ignore it.
// The step 2 is O((n-k)*logk)

3) Finally, MH has k largest elements and root of the MH is the kth largest
element.

Time Complexity: O(k + (n-k)Logk) without sorted output. If sorted output is needed
then O(k + (n-k)Logk + kLogk)

All of the above methods can also be used to find the kth largest (or smallest)
element.

---------------------------------------------------------------

Count No. of ways to read nth stair using 1 2 and 3 steps

[Link]

#include<bits/stdc++.h>
using namespace std;
map<long,long> memo;
long long nSteps(long long n,bool flag)
{
if(n==0) return 1;
long key=n;
long a=0,b=0,c=0,total=0;
if([Link](key))
{
return memo[key];
}
if(n-1>=0)a = nSteps(n-1,flag);
if(n-2>=0)b = nSteps(n-2,flag);
if(!flag && n-3>=0)c = nSteps(n-3,flag);
total = a+b+c;
memo[key] = total;
return total;
}

int main()
{
long long n;
cin>>n;
cout<<nSteps(n,false);
return 0;
}

---------------------------------------------------
isSubsetSum Problem

Find the subset... based problem

Aggressive Cows (Monotonic function)

Find the element at index if the sorting is performed without sorting the array.

Permutation of array

Median of two sorted arrays

Find the rank of subset of string in lexicographic order

Vertical Height of Binary Tree

Lowest Common Ancestor of Binary Search Tree

AVL Tree

Print Elements at every level of BST

Linked List based problem

Merge Sort in LinkedList

1 D Array
2 D Array
Activity Selection Problem
� Banker Algorithm
� Binary tree/binary search tree
� Bit Manipulation
� Character Matching
� Graph
Graph Traversal Algorithm
� Hash Map
� Math/Logic
� Optimization Algorithm
� Palindrome
� Pattern Searching
� Priority Queue�
Recursion
� Searching
� Sliding Window
� Sorting
String Manipulation
� String Matching
� Tree Traversal Algorithm

Questions Done :-
Median of two sorted arrays
Check BST
DFS
BFS
Pattern matching using KMP
Wildcard Pattern matching
Paper Cut into minimum number of squares
Longest Pallindrome
Print All Partition of k subset sum
Partition Problem
Partition of set into two subset of equal sum

/*

*/

-----------------------

Permutation of a string
Coin change problem
Breadth First Search
Depth First Search
Binary Weighted Graph
Dijkstra's Algorithm
Floyd Warshall // not done
Bellman Ford
Infix to Prefix
Evaluation of Prefix
Infix To Postfix
Evaluation of postfix
quickSort(with and without recursion)
merge sort (with and without recursion)
linear sort
bubble sort
selection sort
heap sort
radix sort
shell sort // not done
insertion sort
Huffman Coding
Prim's Algo

--------------------------------------

Kruskal Algo

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
const int MAX = 1e4 + 5;
int id[MAX], nodes, edges;
pair <long long, pair<int, int> > p[MAX];

void initialize()
{
for(int i = 0;i < MAX;++i)
id[i] = i;
}

int root(int x)
{
while(id[x] != x)
{
id[x] = id[id[x]];
x = id[x];
}
return x;
}

void union1(int x, int y)

{
int p = root(x);
int q = root(y);
id[p] = id[q];
}

long long kruskal(pair<long long, pair<int, int> > p[])

{
int x, y;
long long cost, minimumCost = 0;
for(int i = 0;i < edges;++i)
{
// Selecting edges one by one in increasing order from the beginning
x = p[i].[Link];
y = p[i].[Link];
cost = p[i].first;
// Check if the selected edge is creating a cycle or not
if(root(x) != root(y))
{
minimumCost += cost;
union1(x, y);
}
}
return minimumCost;
}

int main()
{
int x, y;
long long weight, cost, minimumCost;
initialize();
cin >> nodes >> edges;
for(int i = 0;i < edges;++i)
{
cin >> x >> y >> weight;
p[i] = make_pair(weight, make_pair(x, y));
}
 // Sort the edges in the ascending order
sort(p, p + edges);
minimumCost = kruskal(p);
cout << minimumCost << endl;
return 0;
}

-------------------------------------------------------------------

8 Queen's Problem
Rat-maze problem
Hamiltonian Cycle
Knapsack Algorithm & 0/1 Knapsack Problem
Job Sequencing Algorithm
Travelling salesman problem
Longest common subsequence
Multistage Graph
HopCroft-Karp for Maximum pattern matching
Jarvi's Algorithm or wrapping
Subset sum
Knight Tour's Problem
Questions based on Pallindrome
Rabin-Karp Algorithm
KMP algorithm
Finite Automata
Edit distance
Longest Pallindromic subsequence