Posts

Minimum Number of Insertion, Deletion and Updation to convert one string to another - Dynamic Programming

In today's post, we will be seeing on how to convert a given string to another with the minimum number of insertions, deletions or updations. I'm considering the fact that converting string A to string B will take the same number of operations as converting string B to string A, only the nature of the operation is different (insertion instead of deletion).

The Algorithm

Let us consider converting string A to string B and let length(string A) > length(string B). So converting string A to string B would take a series of deletion operations followed by updations. The only thing that we need to consider while deleting is that we need to maximize the number of common characters at the same indices after deleting. Let me take an example to explain.

Let string A = "bacad" and string B = "bece". The difference between the length of A and B is 1 and so we need to delete one character. There are 5 characters in string A and so there are 5 different deletions possi…

Array of 3 Pointers

In today's problem we are given 3 sorted arrays. Let A, B, C be the 3 arrays. We need to find a value such that max(abs(A[i] - B[j]), abs(B[j] - C[k]), abs(C[k] - A[i])) is minimum. Consider the following example for a better understanding.

Input

A : [1, 4, 10]
B : [2, 15, 20]
C : [10, 12]

Output

5

Explanation

We choose 10 from A, 15 from B and 10 from C. Therefore, max(abs(10 - 15), abs(15 - 20), abs(10 - 10)) is 5, which is the minimum value possible.

Solution Approach

We use a 3 pointer approach to solve this problem. The 3 pointers are i, j and k which correspond to the indices of A, B and C arrays.

Initialise a result variable to INT_MAX.Run a loop until the end of one of the array's is reached. Find the maximum of the difference between the 3 elements in each iteration. If the maximum value found is the difference between A[i] and B[j], increment the pointer value of the smaller of the two elements. Update the result value if the difference is smaller than the previous resul…

Finding the sum of N Biggest elements in Binary Search Tree

Image
Trees look kind of complicated when you get started with them. But they are really fun when you are a master of recursion concepts. In today's problem we are given a binary search tree and a number N. We have to find the sum of the N biggest elements in the BST, given N <= number of elements in the BST.

Sample IO



Solution Approach

This problem can be solved using recursion. Binary Search Tree, for those of you who are not aware of, is a tree in which the elements in the right child of every node is always bigger than the node itself and every element in the left child of any node is always smaller than the node itself. So basically while solving this sum we have to just make sure that there is no element to the right of the current node and add it until the number of elements we've added reaches N. The algorithm is given below.

Let,
result be the name of the variable storing the value of the sum
sum be the name of the function
k be the number of elements added already
N be the n…

Printing All Palindromic Strings in a Matrix

We are given a character matrix and we need to find the list of all the palindromic strings in that matrix starting from the top left corner to the bottom right corner i.e the first character of all the strings must be the top left character in the matrix and the last character must be the bottom right character. The other important condition is that you can only move either towards the right or towards the bottom while tracing a string in the matrix.

Sample Input

Input Matrix is given below

a a a b
b a a a
a b b a

Sample Output

aaaaaa (0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (1, 3) -> (2, 3)
aaaaaa (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 3) -> (2, 3)
abaaba (0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> (2, 2) -> (2, 3)

Solution Approach

We can follow a backtrack approach to solve this problem. According to Wikipedia backtracking is defined as :

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, not…

Minimum Number of Hops to Reach the End of an Array

Each element of an array indicates the length of the hop from that particular index. For example : if A[i] is 3 then you can jump to A[i+1] or A[i+2] or A[i+3] from the ith index. The problem states that, find the minimum number of hops required to reach the end of the array. If an element is 0, then it would mean that no other element can be reached from that particular element.

Solution Approach

It can be easily solved using Dynamic Programming. I've used a recursive approach to solve the above given problem. There are a few points to keep in mind before starting with the solution.

1. We need to know when a particular path would end - A particular path would end if you can reach the last element from the current element. i.e i + A[i] >= Length of the Array.

2. We need to find the minimum of the number of hops required from all the elements that can be reached from the current element, recursively.

Solution






In the above program the input is given as 1, 2, 3, 4, 5. The output in…

Finding the Number of Trailing Zero's in Factorial of a Number

Factorial of a number is one of the most basic sums that you'll be doing whenever you learn a programming language. Finding the number of trailing zero's in the factorial of a number sounds pretty simple right ? You can just find the factorial of the number and you can run a while loop until factorial % 10 == 0 and increment a counter.

But it doesn't work like that. There is no data type in C which can hold the factorial of 21 or greater. So you cannot simply find the factorial and find the number of zero's. The solution for the problem is pretty simple. You can just find the number of two's and number of five's (5 x 2 = 10) in every number that constitutes the factorial and return the number of five's. That's it. Sounds very simple right ? Yes it is.

Program


#include <iostream>usingnamespace std;  int zeros(int A){  int two = 0;  int five = 0;  int temp;  for(int i = 2; i <= A; i++){          temp = i;  while(temp % 2 == 0 || temp % 5 == 0){

Finding a Single Number amongst Repeated Numbers [Repeated Twice]

Image
Ever came across a problem which asks you to find a single number (or a number that occurs once) amongst a set of repeated numbers (which are repeated twice each) ? Well, it is a pretty common problem and is asked a lot of times.

There are many ways to solve the problem. The most obvious but inefficient approach to solve the problem would be to use a brute force approach where you can loop through the list multiple times to find the repeated numbers or you can have a count of all the numbers occurring and just return the number that has a count of 1. But an efficient way to solve the problem would be to use the bitwise operators.

The basic idea behind the solution is that XOR of two same numbers is 0.

Problem

Sample Input : 1 2 3 2 3

Sample Output : 1

We will simply loop through all the elements in the array and XOR each of them and save them in a variable.

So we will have 1 XOR 2 XOR 3 XOR 2 XOR 3. 2 XOR 2 and 3 XOR 3 would fetch 0, leaving us with 0 XOR 1. And this would obviously ret…