Competitive Coding

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...

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  strin...

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.geeksforgee...

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++)     {         ...

  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...

  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:   ...