Archive for June, 2013

Today we have to write a program for finding the balance index in a given array. This problem can be solved on O( n ) time.

Approach 1

1. Loop Through the array and calculate the sum ,let’s assume sum is equal to arraySum.
2. Now again again iterate over array elements
1. Calculate the sum of element say it is leftsum
2. calculate the difference between arraySum and current Element in arraySum
3. if arraySum is equal to leftSum, then current array index is the balance index.
3. Otherwise return –1, means balance index is not present in the array.

Code:

```        public static int BalanceIndex(int[] input)
{
int arraySum = 0;
int leftSum = 0;
int balnaceIndex = -1;
//Calculate the sum of all elements
for (int i = 0; i < input.Length; i++)
{
arraySum = arraySum + input[i];
}

Console.WriteLine("Sum of Array Elements : " + arraySum);

for (int i = 0; i < input.Length; i++)
{
leftSum = leftSum + input[i];
arraySum = arraySum - input[i];
if (arraySum == leftSum)
{
balnaceIndex = i;
return balnaceIndex;
}
}

if (leftSum != arraySum)
{
return -1;
}
return balnaceIndex;
}```

Test Case

private static void BalanceIndexTest()

{

int[] arr = new int[] { -7, 1, 5, 2, -4, 3, 0,8 };

Console.WriteLine("Balance index for " + string.Join(",", arr) + " is : " + ArrayProblems.BalanceIndex(arr));

int[] arr1 = new int[] { 1, 3, 4, 6, 7, 2, 5, 9, 1, 11, 9, 6, 5, 8, 9, 1 };

Console.WriteLine("Balance index for " + string.Join(",", arr1) + " is : " + ArrayProblems.BalanceIndex(arr1));

int[] arr2 = new int[] { -7, 1, 5, 2, -4, 3, 0};

Console.WriteLine("Balance index for " + string.Join(",", arr2) + " is : " + ArrayProblems.BalanceIndex(arr2));

int[] arr3 = new int[] { -7 };

Console.WriteLine("Balance index for " + string.Join(",", arr3) + " is : " + ArrayProblems.BalanceIndex(arr));

}

Output

Sum of Array Elements : 8

Balance index for -7,1,5,2,-4,3,0,8 is : –1

Sum of Array Elements : 87

Balance index for 1,3,4,6,7,2,5,9,1,11,9,6,5,8,9,1 is : –1

Sum of Array Elements : 0

Balance index for -7,1,5,2,-4,3,0 is : 5

Sum of Array Elements : -7

Balance index for -7 is : -1

Given a single linked list, we have to detect loop. For this we will use two pointers called slow and fast. We will increment slow by one and fast by two. once both these pointers meet, this is the node from were loop is present

```        public void DetectLoop(Node<T> node)
{
Node<T> slow = node;
Node<T> fast = node;

while (slow != fast && fast.Next != null)
{
slow = slow.Next;
fast = fast.Next.Next;
if (slow == fast)
{
Console.WriteLine("Loop is detected");
return;
}
}
Console.WriteLine("There is no loop");

}```

Input  : Number of Rows

Output:

1
121
12321
1234321
123454321

Code

```        public static void PrintNumberPattern2(int rows)
{
int i, j, k;
//Loop for number of Rows
for (i = 1; i <= rows; i++)
{
// Loop for printing numbers in increasing order
for (j = 1; j < 2 * i + 1; j++)
{
Console.Write(j);
if (j >= i)
{
break;
}
}
// Loop for printing numbers in decreasing order
for (k = j - 1; k > 0; k--)
{
Console.Write(k);
}
Console.WriteLine("");
}
}```

Today we have to write a program for rotating a given matrix by 90 degree. This code only works with square matrix.

Code

```        public static void MatrixRotation<T>(T[,] matrix)
{
Console.WriteLine("\n Input Matrix");
Print2DMatrix(matrix);
int row = matrix.GetLength(0);
int column = matrix.GetLength(1);

T temp;
for (int i = 0; i < row; i++)
{
for (int j = i + 1; j < column; j++)
{
temp = matrix[j, i];
matrix[j, i] = matrix[i, j];
matrix[i, j] = temp;
}
}

for (int i = 0; i < row / 2; i++)
{
for (int j = 0; j < column; j++)
{
temp = matrix[j, i];
matrix[j, i] = matrix[j, row - i - 1];
matrix[j, row - i - 1] = temp;
}
}
Console.WriteLine("\n Rotation matrix");
Print2DMatrix(matrix);

}

private static void Print2DMatrix<T>(T[,] matrix)
{
Console.WriteLine("--------------\n");
int row = matrix.GetLength(0);
int column = matrix.GetLength(1);

for (int i = 0; i < row; i++)
{
for (int j = 0; j < column; j++)
{
Console.Write(matrix[i, j] + " ");
}
Console.WriteLine(" ");
}

}```

Result

Input Matrix

————–

11 12 13 14 15

21 22 23 24 25

31 32 33 34 35

41 42 43 44 45

51 52 53 54 55

Rotation matrix

————–

51 41 31 21 11

52 42 32 22 12

53 43 33 23 13

54 44 34 24 14

55 45 35 25 15

Input Matrix

————–

A B C D

E F G H

I J K L

M N O P

Rotation matrix

————–

M I E A

N J F B

O K G C

P L H D