Competitive Programming

 Biggest Plus Sign in Matrix (Dynamic Programming) PROBLEM STATEMENT : The program must accept an integer matrix of size R*C containing only 0s and 1s as the input. The program must find the biggest plus sign ( + ) formed by 1s in the given matrix. Then the program must print the length of the edge of the biggest plus sign (Edge length = the number of cells from the middle cell of the plus sign to one of the four ends). All four edges of the plus sign must be equal. If the plus sign is not present in the matrix, then the program must print -1 as the output. Boundary Condition(s): 3 <= R, C <= 50 Input Format: The first line contains R and C separated by a space. The next R lines, each contain C integers separated by a space. Output Format: The first line contains the length of the edge of the biggest plus sign Example Input/Output 1: Input: ( ) 6 7 0 0 1 0 1 0 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 Output: 3 Explanation:  Th...

Denomination (Greedy Algorithm) PROBLEM STATEMENT : John is now the cashier of his newly opened business. He has a lot of notes of each denomination (1,2,5,10,20,50,100,500,1000). He has to pay his customer a change of N rupee. Find him the minimum number of denominations required to pay back the change. Input format : First-line contains an integer T where T is the number of test cases. For every Test case: The next line contains N.  Output format : For every test case print the minimum number of denominations required to pay back the change in a new line.  Constraints : 1 <= T <= 70 1 <= N <= 10 5   Time Limit : 1 second Example Input/Output 1: Input: ( ) 5 35 24 100 90 23 Output: 3 3 1 3 3 Input/Output Explanation: Input: N = 90 Output: 3 Explanation: 1 note of 50 and 2 notes of 20 will give 90 Input/Output Explanation: Input: N = 100 Output: 1 Explanation: 1 note of 100 is enough to give 100 SOLUTION :  (CPP) Hint:    We can us...

 Positions - Queen & Knight (Greedy Algorithm) PROBLEM STATEMENT : Given a position of Queen and Knight. Form 8X8 matrix with all position filled with '0' and replace given Queen position with 'Q' and replace given Knight position with 'K'. Find number of possible moves where Queen can be moved on a chessboard from given position and replace the positions with 'q' and Find number of possible moves where Knight can be moved on a chessboard from given position and replace the positions with 'k' and if both queen and knight meets in same position then that position should be replaced with 'x'. Input Format: First line consist of row and column position of Queen First line consist of row and column position of Knight Output: 8X8 matrix with all possible moves of Queen and Knight. Example Input/Output 1: Input: ( ) 2 3 4 8 Output: 0 q q q 0 0 0 0 q q Q q q q x q 0 q q q 0 k 0 0 q 0 q 0 q 0 0 K 0 0 q 0 0 x 0 0 0 0 q 0 0 0 x 0 0 0 q 0 ...

Trailing zeroes in factorial  PROBLEM STATEMENT : Given T testcases and For each testcase an integer N is given as the input. For each input, Find the number of trailing zeroes in N!.    Expected Time Complexity: O(logN) (for Finding Number of trailing Zeroes for each testcase) Expected Auxiliary Space: O(1) Example 1: Input: ( ) 5 Output: 1 Explanation: 5! = 120 so the number of trailing zero is 1. Example 2: Input: ( ) 4 Output: 0 Explanation: 4! = 24 so the number of trailing zero is 0. HINT :     Trailing 0s in n! = Count of 5s in prime factors of n!                 = floor(n/5) + floor(n/25) + floor(n/125) + .. SOLUTION :  Copy Code #include <iostream> using namespace std; int main() { int t; cin>>t; while(t--) { int n,noOfZeroes=0; cin>>n; Trailing 0s in n! = Count of 5s in prime factors of n! while(n>0) { noOfZeroes+=(n/5); n/=5; } ...

  The Next Palindrome PROBLEM STATEMENT : A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros. Input The first line contains integer t, the number of test cases. Integers K are given in the next t lines. Output For each K, output the smallest palindrome larger than K. Example Input: 2 808 2133 Output: 818 2222 Warning: large Input/Output data, be careful with certain languages SOLUTION :  Copy Code #include <iostream> #include<string> using namespace std; int main() { long long int i,l; int t; cin>>t; while(t--) { string k,x; cin>>k; x=k; l=k.size(); for(i=l/2;i<l;++i) x[i]=x[l-i-1]; if(x>k) { cout<<x<<...

Infix to Postfix Expression Infix expression: The expression of the form a op b. When an operator is in-between every pair of operands. Postfix expression: The expression of the form a b op. When an operator is followed for every pair of operands. PROBLEM STATEMENT : Transform the algebraic expression with brackets into postfix form. Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one f=postfix form (no expressions like a*b*c). Input : t [the number of expressions <= 100] expression [length <= 400] [other expressions] Text grouped in [ ] does not appear in the input file. Output : The expressions in postfix form, one per line. Example Input: 3 (a+(b*c)) ((a+b)*(z+x)) ((a+t)*((b+(a+c))^(c+d))) Output: abc*+ ab+zx+* at+bac++cd+^* SOLUTION :  Note : We can solve this problem using STACK. Copy Code #include <bits/stdc++.h> int priority(char c) { if(c=='+'|...