Posts

Karatsuba Algorithm

  Given two binary strings that represent value of two integers, find the product of two strings. For example, if the first bit string is “1100” and second bit string is “1010”, output should be 120. Input: First line consists of T test cases. Only line of every test case consists of 2 binary strings. Output: Single line output, print the multiplied value. Constraints: 1<=T<=100 1<=Length of string<=100 Example: Input: 2 1100 01 01 01 Output: 12 1 The link of this problem is  https://practice.geeksforgeeks.org/problems/karatsuba-algorithm/0 Solution(CPP): #include<iostream> using namespace std; int main() {     int t;     cin>>t;     while(t--)     {         string a;         string b;         cin>>a>>b;         stack<int> s1;         stack<int> s2;         for(int i=0;i<a.length();i++)         {             s1.push(a[i]-'0');         }         for(int i=0;i<b.length();i++)         {             s2.push(b[i]-'0');  

Longest Increasing Subsequence

Given a sequence  A  of size  N , find the  length  of the  longest increasing subsequence  from a given sequence . The longest increasing subsequence means to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible.This subsequence is not necessarily contiguous, or unique. Note:  Duplicate numbers are not counted as increasing subsequence. Input: The first line contains an integer T, depicting total number of test cases. Then following T lines contains an integer N depicting the size of array and next line followed by the value of array. Output: For each testcase, in a new line, print the Max length of the subsequence in a separate line. Constraints: 1 ≤ T ≤ 100 1 ≤ N ≤ 1000 0 ≤ A[i] ≤ 300 Example: Input : 2 16 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 6 5 8 3 7 9 1 Output: 6 3 Explanation: Testcase 2:  Longest increasing subsequence is of size 3 with elements (there are many

Design a tiny URL or URL Shortner

Design a system that takes big URLs like “ http://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/ ” and converts them into a short  6 character URL . It is given that URLs are stored in database and every URL has an associated integer   id .  So your program should take an integer id and generate a 6 character long URL.  A URL character can be one of the following A lower case alphabet [‘a’ to ‘z’], total 26 characters An upper case alphabet [‘A’ to ‘Z’], total 26 characters A digit [‘0′ to ‘9’], total 10 characters There are total 26 + 26 + 10 = 62 possible characters. So the task is to convert an integer (database id) to a base 62 number where digits of 62 base are "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" Input: The first line of input contains an integer T denoting the number of test cases.  The second line consists of a long integer. Output: For each testcase, in a new line, print the  shortened  string in the first line and conve

Boolean Matrix Problem

Given a boolean matrix   mat[M][N]   of size   M   X   N , modify it such that if a matrix cell   mat[i][j]   is   1   (or true) then make all the cells of ith row and jth column as   1 . Input: The first line of input contains an integer  T  denoting the number of test cases. The first line of each test case is r and c, r is the number of rows and c is the number of columns. The second line of each test case contains all the elements of the matrix in a single line separated by a single space. Output: Print the modified array. Constraints: 1 ≤ T ≤ 100 1 ≤ r, c ≤ 1000 0 ≤ A[i][j] ≤ 1 Example: Input: 3 2 2 1 0 0 0 2 3 0 0 0  0 0 1 4 3 1 0 0 1 0 0 1 0 0 0 0 0 Output: 1 1 1 0 0 0 1  1 1 1 1 1 1 1 1 1 1 0 0 Explanation: Test case 1:  Since only first element of matrix has 1 (at index 1,1) as value, so first row and first column are modified to 1. The link of this problem is  https://practice.geeksforgeeks.org/problems/boolean-matrix-problem/0 Solution: CPP #include<iostream> using nam

Floyd Warshall algorithm and it's applications.

The floyd warshall algorithm is for solving the All Pairs Shortest Path problem. The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph. INPUT : Input will be a distance matrix (let say dis) , where dis[i][j] will represent the distance between the ith and jth node in the graph. and you have to input 2 nodes (a and b) between whom you want to find the shortest distance . OUTPUT: Output will be the shortest distance between the two node a and b. and it will also output the path between the two node through which you can achieve the shortest distance. ...................................................................................................................................................................... #include<bits/stdc++.h> using namespace std; #define inf 1000 void iter(int dis[][5],int seq[][5],int k) {     for(int i=0;i<5;i++)     {          for(int j=0;j<5;j++)          {               if(i<j

Squares in N*N Chessboard

  Find total number of Squares in a   N*N   chessboard. Input: The first line contains an integer  T , depicting total number of test cases. Then following T lines contains an integer N that is the side of the chessboard. Output: Each separate line showing the maximum number of squares possible. Constraints: 1 ≤ T ≤ 100 1 ≤ N ≤ 100 Example: Input: 2 1 2 Output: 1 5 Solution: CPP #include<iostream> using namespace std; int main() {      int t;      cin>>t;      while(t--)      {          int n;          cin>>n;          int sum=0;          for(int i=1;i<=n;i++)          {              sum=sum+i*i;          }          cout<<sum<<endl;      } return 0; }

Primality Test

  For a given number   N   check if it is prime or not. A prime number is a number which is only  divisible by 1 and itself. Example 1: Input: N = 5 Output: Yes Explanation: 5 is a prime number. Example 2: Input: N = 4 Output: No Explanation: 4 is not a prime number. Your Task: You don't need to read input or print anything. Your task is to complete the function   isPrime()  that takes  N  as  parameter  and returns  True  if  N  is prime else returns  false .  Expected Time Complexity  : O(N 1/2 ) Expected Auxilliary Space  :  O(1) Constraints: 1 <= N <= 10 9      The link of this problem is   https://practice.geeksforgeeks.org/problems/primality-test/1 Solution: Python3 import math def isPrime(N):     if N<2:         return False     for i in range(2,int(math.sqrt(N))+1):         if N%i==0:             return False     return True def main():     T=int(input())     while(T>0):         N=int(input())         if(isPrime(N)):             print("Yes")         el