Maximum single sell profit from stock

 Posted on April 30, 2015  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

Problem Suppose we are given an array of n integers representing stock prices on a single day. We want to find a pair (buyDay, sellDay), with buyDay ≤ sellDay, such that if we bought the stock on buyDay and sold it on sellDay, we would maximize our profit. OR Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in arr[]. [Read More]
max  maxima  stock  divide and conquer  Dynamic Programming  DP  minima  array 

Count the number of digits in the number

 Posted on May 4, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Given the integer, find the number of digits in the integer. Solution Method 1 - Brute force using loop Keep dividing the number, until it is 0. This will give us the count of number. Java code public static int getSize(long number) { int count = 0; while (number > 0) { count += 1; number = (number / 10); } return count; } Method 2 - Convert to string [Read More]
kodeknight  divide and conquer  count 

k-way merge - Merging k sorted arrays of n elements

 Posted on January 19, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Given k sorted arrays of size n each, merge them and print the sorted output. Example: **Input:** k = 3, n = 4 arr = { {1, 3, 5, 7}, {2, 4, 6, 8}, {0, 9, 10, 11}} ; **Output:** 0 1 2 3 4 5 6 7 8 9 10 11 Method 1 - Merging from 1 array to other It does so by using the “merge” routine central to the merge sort algorithm to merge array 1 to array 2, and then array 3 to this merged array, and so on until all k arrays have merged. [Read More]
kodeknight  merge  divide and conquer  sorting  array  two-sorted-arrays  min-heap  sorted-array 

Integer Multiplication using Karatsuba algorithm

 Posted on August 14, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Normal Integer method If we consider the integer multiplication, we need 2 integers and output is also integer. Suppose we have to multiply 5678*1234. In the normal way, we will realize following: 5678 X 1234 \------------ 22712 //first number multiply as is i.e. 4\*5678 17034- //2nd time, shift (left) and then multiply the number as 3\*5678 11356-- //shift twice 5678--- //shift thrice \------------ 7006652 ```So, each time we multiply, depending on the digit of the 2nd number, we shift and then multiply. [Read More]
master-method  kodeknight  time complexity  divide and conquer  incomplete  multiplication 

Closest Pair Algorithm

 Posted on August 4, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Here we will discuss about the closest pair algorithm. Input : A set p = { p1,p2, … pn} of n points in the plane (R2) Notation d(pi , pj) = Euclidean distance. d = x Assumption - All points have distinct x-coordinates distinct y-coordinates. Brute force method Say you are given a set of points in the plane and you want to find the two points closest to one another. [Read More]
Algorithms  kodeknight  divide and conquer  Data Structure  plane 

Master Method for Solving Recurrences

 Posted on August 4, 2013  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Why Master method ? - Master method helps us analysing algorithms with their running time. So, lets consider the integer multiplication - here. Now we get equation 1. The way we reason about recursive algorithm like these is with the help of recurrence. Recurrences What is recurrence? T(n) = max number of operations this algorithm needs to multiply 2 n digit numbers. Recurrence is to express T(n) in terms of recursive calls. [Read More]
master-method  Algorithms  kodeknight  time complexity  divide and conquer  Data Structure  Omega Time complexity 

Strassen's Subcubic Matrix Multiplication Algorithm

 Posted on August 4, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

A Review on Matrix Multiplication Given two 2 nxn matrices X, Y and their product matrix Z, X.Y = Z we know that Zij = (ith row of X) . (jth column of Y). So, we take row from X, and column from Y. zij = ∑xik . ykj where k is 1 < k < n. For eg. : Let X = a b and Y = e f [Read More]
Algorithms  kodeknight  divide and conquer  matrix-multiplication  recursion  Data Structure  matrix 

Median of 2 sorted arrays of equal size n

 Posted on September 13, 2011  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

Question  There are 2 sorted arrays A and B. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n)) Solution Before going to solution what is the median. What is Median? Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample, a population, or a probability distribution, from the lower half. [Read More]
Adobe  kodeknight  Microsoft  yahoo  divide and conquer  Amazon  array  two-sorted-arrays  median  incomplete  two-arrays  sorted-array 

Divide and Conquer

 Posted on July 5, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

In this section we consider backtracking algorithms. As in the preceding section, we view the problem to be solved as a sequence of decisions. A backtracking algorithm systematically considers all possible outcomes for each decision. In this sense, backtracking algorithms are like the brute-force algorithms discussed in the preceding section. However, backtracking algorithms are distinguished by the way in which the space of possible solutions is explored. Sometimes a backtracking algorithm can detect that an exhaustive search is unnecessary and, therefore, it can perform much better. [Read More]
Algorithms  kodeknight  divide and conquer