Today we will discuss a common problem. The problem is, you are given a string S, you have to find the longest palindromic substring in S. For example, S = abcbsd, here our desired answer is bcb with length 3. Solution: This problem can be solved in many ways. One of them is DP solution and another is Expand Around Center. DP: DP solution is a very straight cut solution. We go through all the substrings of the main string S and check each substring is palindrome or not and find the longest substring if it is palindrome. Here we do DP in the palindrome checking part. Here is the Code. Complexity O(n^2) . #include<bits/stdc++.h> using namespace std ; string s ; int dp [ 1005 ] [ 1005 ] ; ///dp[l][r] means is substring s[l...r] is a palindrome or not int isPalindrome ( int left, int right ) { if ( left >= right ) return 1 ; if ( dp [ left ] [ right ] ! = - 1 ) return dp [ left ] [ right ] ; int result = 0 ; if ( s ...
Number of Divisors(NOD) Given N you have to find the number of divisors of N. Solution: Step 1: Generating Prime using Sieve of Eratosthenes Step 2: Count Divisors using prime factorization CODE: long long NOD_using_factorization ( long long n ) /// O(lof2(N)) { long long sqrtn = sqrt ( n ) ; long long tmp = 1 ,divisors = 1 ; for ( int i = 0 ; i < prime. size ( ) && prime [ i ] <= sqrtn ; i ++ ) { ///if ( sieve[n] == 0 ) break; ///*Checks if n is prime or not*/ Please comment This line if n > 1e7 if ( n % prime [ i ] == 0 ) { tmp = 1 ; while ( n % prime [ i ] == 0 ) { n / = prime [ i ] ; tmp ++ ; } divisors * = tmp ; sqrtn = sqrt ( n ) ; ...
Comments
Post a Comment