# Posts Tagged ‘algorithms’

## Maximum subarray in an array

Posted by guptaradhesh on March 26, 2014

``````         /*
* Returns a maximum sum value in an array of integers
*/
public int maxScan(int[] array)
{
if(array.length == 0) return -1;
else if(array.length == 1)
return array[0];
else
{
int maxSum = array[0];
int current_max = array[0];
for(int i = 1; i < array.length; i++)
{
current_max = Math.max(array[i], current_max + array[i]);
maxSum = Math.max(maxSum, current_max);
}
return maxSum;
}
}``````

## Print matrix in a sprial order

Posted by guptaradhesh on August 22, 2013

Recursive Solution (Java):

```public class PrintMatrixSpiral
{
public static void main(String[] args)
{
int[][] matrix =
{
{ 2, 4, 6, 2, 5, 7 },
{ 2, 5, 7, 8, 9, 3 },
{ 6, 4, 7, 3, 5, 7 } };

printSpiral(matrix);
}

public static void printSpiral(int[][] matrix)
{
printSpiral(matrix, 0);
}

private static void printSpiral(int[][] matrix, int depth)
{
if (matrix == null && matrix.length == 0)
return;
int rows = matrix.length;
int cols = matrix[0].length;
if (2 * depth > Math.min(rows, cols))
return;
for (int i = depth; i < cols - depth - 1; ++i)
{
System.out.print(matrix[depth][i] + ",");
}
for (int i = depth; i < rows - depth - 1; ++i)
{
System.out.print(matrix[i][cols - depth - 1] + ",");
}
for (int i = rows - depth; i > depth; --i)
{
System.out.print(matrix[rows - depth - 1][i] + ",");
}
for (int i = rows - depth - 1; i > depth; --i)
{
System.out.print(matrix[i][depth] + ",");
}
printSpiral(matrix, ++depth);
}
}

```

Posted in java, puzzles/ algorithms, tech | Tagged: , , , , | Leave a Comment »

## Find the index i and j of an array where j>i and a[j] – a[i] is maximum

Posted by guptaradhesh on March 27, 2013

Given an unsorted array, find the index i and j such that, j>i and (a[j] – a[i]) is maximum?

A linear time solution which I find pretty elegant:

``````       private void MaxDiff(int[] a)
{
int min = a[0]; // assume first element as minimum
int maxdiff = 0;
int posi = -1, posj = -1, minpos = 0;

for (int i = 1; i < a.Length; i++)
{
if (a[i] < min)
{
min = a[i];
minpos = i;
}
else
{
int diff = a[i] - min;
if (diff > maxdiff)
{
maxdiff = diff;
posi = minpos;
posj = i;
}
}
}
System.out.format("i=%d, j=%d",posi,posj);
}``````

## Permutations of a String

Posted by guptaradhesh on February 4, 2013

``````public  static void permutation(String str) {
permutation("", str);
}

private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
}
}``````

Posted in java, puzzles/ algorithms | Tagged: , , , | 1 Comment »

## compute max-depth of a binary tree

Posted by guptaradhesh on December 8, 2010

int maxDepth(struct node* node)

{

if (node==NULL) { return(0);

}

else {

int leftDepth = maxDepth(node->left);

int rightDepth = maxDepth(node->right);

if (leftDepth > rightDepth)

return(leftDepth+1);

else

return(rightDepth+1);

} }

## algorithm to determine number of 1’s in binary representation of a number

Posted by guptaradhesh on November 3, 2010

To determine the number of set bits in the binary representation of a number, the basic method would be-
Find if the least significant digit of the number is 1 or not by performing AND operation with 1. Keep shifting the bits and when there are no 1’s left, the number becomes zero.

This algorithm takes O(n) time.

I read an algorithm which performs real better. I actually likes the solution where in we can deduce the number of 1’s in O(m) time where m is the number of 1’s present in the number.

The basic login is to recognize a pattern where, ‘when we perform n AND (n-1) : last 1 bit of the number sets to zero’. So, the number of times we can do this will give the number of 1’s present in the number.

A short also snippet would be-

int numberOfOnes ( int num )
{
int numOfOnes = 0;
while( num != 0 ){
num = num & (num – 1);
numOnes++;
}
return numOfOnes;
}

Posted in puzzles/ algorithms | Tagged: , , | 1 Comment »