Competitive Programming

 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=='+'|...

Prime Numbers in Range   ( Segmented Sieve of Eratosthenes) Segmented Sieve is used for finding prime numbers in the given range (low and high) with less auxiliary space . The problem with simple Sieve of Eratosthenes is that it takes more memory for given long ranges (low and high). PROBLEM STATEMENT : Given a range [low, high], print all primes in this range? Input : The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space. Output : For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.   For example, Input :   2 1 10 3 5 Expected Output :   2 3 5 7 3 5 SOLUTION : Copy Code #include <bits/stdc++.h> using namespace std; int main(int argc, char** argv) { int t; cin>>t; while(t--) { int low,high,i...

Prime Numbers   ( Sieve of Eratosthenes) The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million  (For more understanding, Ref  Wiki ).         PROBLEM STATEMENT : Given a number n, print all primes smaller than or equal to n.   Input : 100   Expected Output : 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 SOLUTION : To Solve this problem more effectively, We use Sieve of Eratosthenes algorithm. Time Complexity : O(n*log(log(n))) For Sieve of Eratosthenes algorithm Auxiliary  Space : O(n) Here auxiliary space is Boolean Array prime Never Stop Learning !!