Algorithm improvement

Question

My job-interview task was to:

found one array item which satisfying condition: after you remove it, the multiplication of remaining items will be the highest. For instance: -5, -3, -1, 4, 6 => -1

My solution was recognized as non optimized enough. Could you produce me with some suggestions on algorithm improvements?

My solution was:

public int FindRequiredValue(int[] IntArray)
    {
        try
        {
            Array.Sort(IntArray);

            var first = IntArray.First();
            var last = IntArray.Last();

            if (first >= 0)
                return first;
            else
                if (last < 0)
                    return (IsEven(IntArray.Count()) ? first : last);
                else
                {
                    if (last == 0)
                    {
                        var lastindex = IntArray.Count() - 1;
                        if (IntArray[lastindex - 1] == 0)
                            return first;
                        else
                            return IsEven(lastindex) ? 0 : first;
                    }
                    else
                    {
                        var firstpositiveindex = IntArray.Select((x, i) => new { element = x, index = i }).First(y => (y.element > 0)).index;

                        if (IntArray[firstpositiveindex - 1] < 0)
                            return IsEven(firstpositiveindex) ? IntArray[firstpositiveindex] : IntArray[firstpositiveindex - 1];
                        else
                            if (IntArray[firstpositiveindex - 2] < 0)
                                return IsEven(firstpositiveindex - 1) ? 0 : first;
                            else
                                return first;
                    }
                }
        }
        catch (Exception ex)
        {
            throw;
        }
    }

Note that all not-null checks, overflows e.t.c. are checking before the function was called.

Update: possible ways: sort and etc., loop through etc; Any other ideas?

Answer 1

You had no need to sort the array, which requires O(n*log(n)) complexity; you could have done with O(n) solution. That's why, IMHO, your code is suboptimal. Possible implementation:

public int FindRequiredValue(int[] value) {
  if (Object.ReferenceEquals(null, value))
    throw new ArgumentNullException("value");
  else if (value.Length <= 0)
    throw new ArgumentException("Empty arrays can't be proceeded.", "value");

  // Algorithm:
  // if the array contains odd negative numbers print out the maximum among them:
  //   {-1, -2, -3, 4, 5} => -1
  // if the array contains even negative numbers print out the smallest non-negative one:
  //   {-1, -2, 4, 5} => 4
  // if array contains even negative numbers and no non-negative numbers print out the
  // smallest negative one 
  //   {-1, -2, -3, -4} => -4

  int max_Negative = 0;
  int min_Negative = 0;
  int min_NonNegative = -1;
  int negativeCount = 0;

  foreach (int v in value) {
    if (v < 0) {
      negativeCount += 1;

      if ((v > max_Negative) || (max_Negative == 0))
        max_Negative = v;

      if ((v < min_Negative) || (min_Negative == 0))
        min_Negative = v;  
    }
    else {
      if ((v < min_NonNegative) || (min_NonNegative == -1))
        min_NonNegative = v; 
    }  
  }

  if ((negativeCount % 2) == 1)
    return max_Negative;
  else if (min_NonNegative != -1)
    return min_NonNegative;
  else
    return min_Negative; 
}

Answer 2

In this question you will either want to remove the smallest (in absolute value) negative integer if there are odd number of negative integers, or the smallest positive integer if there are even number of negative integers. (zero counts as positive)

So iterate through the array once and keep track of:
1. Lowest in absolute value negative integer.
2. Lowest in absolute value positive integer.
3. Number of negative integers.

After the iteration, remove accordingly.

Complexity: O(N) in time, and O(1) in space.