anunay
BAN USERAnother shot at the problem.
public void ProductOfArrayElements()
{
int[] inputArr = { 1, 2, 3 };
int[] indexArr = { 2, 0, 1 };
int[] output = new int[inputArr.Length];
int leftProd = 1;
for (int i = 0; i < inputArr.Length; i++)
{
output[ i ] = leftProd;
leftProd *= inputArr[indexArr[i]];
}
int rightProd = 1;
for (int i = inputArr.Length - 1; i >= 0; i--)
{
output[i] *= rightProd;
rightProd *= inputArr[indexArr[i]];
}
output.ToList().ForEach(Console.WriteLine);
// Output is [2, 6, 3 ]
// 2 = 1 * 2 ( skipping inputArr[2])
// 6 = 2 * 3 ( skipping inputArr[0])
// 3 = 1 * 3 ( skipping inputArr[1])
}
Sorry, my bad I reread the original problem. I interpreted it incorrectly. The solution I posted above is incorrect, but it is still possible to solve this in O(n) algorithm with O(1) memory, by slightly modifying the solution given in the following post geeksforgeeks.org/?p=7527
- anunay July 09, 2010The original problem statement is not clear. Index is not an array. It is the current index of the array. The input is just two arrays. In the example I posted above index value is i for the current array we are processing.
For better a explanation to a slight variation of this problem please see http:_geeksforgeeks.org/?p=7527
O(n) algorithm with O(1) memory. This algorithm traverses both the arrays twice, once calculation product of numbers on the left and then calculating products on the right side. The result of this traversals is written in the results array.
int[] arr1 = { 1, 2, 3 };
int[] arr2 = { 10, 20, 30 };
int[] output = new int[arr1.Length];
int leftProd = 1;
for (int i = 0; i < arr1.Length; i++)
{
output[i] *= leftProd;
leftProd *= arr1[i];
}
int rightProd = 1;
for (int i = arr1.Length - 1; i >= 0; i--)
{
output[i] *= rightProd;
rightProd *= arr1[i];
}
leftProd = 1;
for (int i = 0; i < arr2.Length; i++)
{
output[i] *= leftProd;
leftProd *= arr2[i];
}
rightProd = 1;
for (int i = arr2.Length - 1; i >= 0; i--)
{
output[i] *= rightProd;
rightProd *= arr2[i];
}
output.ToList().ForEach(Console.WriteLine);
The solution suggested by random does not work if we start from top right edge of the matrix, but it works fine if we start from bottom right and move upwards towards [0,0] element. Here is updated code
public int CountNumberofNegativeNumbersInASortedMatrix()
{
int N = 5;
int [,] arr =
{
{ -3, -2, 3, 4, 5},
{ -4, -3, 2, 3, 4},
{ -5, -4, -1, 1, 2},
{ -6, -5, -2, 0, 1},
{ -7, -6, -3, -2, -1},
};
if ( arr[0,0] >= 0 )
return 0;
if ( arr[N -1 ,N -1] < 0 )
return N -1 * N - 1;
int row = N - 1;
int col = N - 1;
int count = 0; //count is the number of negatives in the matrix
while( row >= 0 && col >= 0 )
{
if(arr[row,col] < 0)
{
count += col + 1 ; //everything on the left of a(row,col)including itself are -ve
row--;
}
else
{
col--;
}
}
return count;
}
public void MaximumDifferenceBetweenTwoElements()
{
//The function assumes that there are at least two
//elements in array.
//The function returns a negative value if the array is
//sorted in decreasing order.
//Returns 0 if elements are equal
//We take difference between the picked element and the minimum element found so far.
//So we need to keep track of 2 things:
//1) Maximum difference found so far (max_diff).
//2) Minimum number visited so far (min_element).
int [] arr = {2, 3, 10, 6, 4, 8, 1};
int maxDiff = arr[1] - arr[0];
int minElement = arr[0];
for (int i = 1; i < arr.Length; i++)
{
if (arr[i] - minElement > maxDiff)
maxDiff = arr[i] - minElement;
if (arr[i] < minElement)
minElement = arr[i];
}
Console.WriteLine(maxDiff);
}
Slight modification to not require a char array
- anunay August 05, 2010