How to remove two elements of collection at the same time? Task about cyclopes lenses

Question

I cant solve this task.

1. There are N cyclopes and an array of N elements.
2. Every element is eyesight value of single cyclop.
3. Every cyclop needs a lens with a value K but he will be okay with lens of value K+1 or K-1.
4. Cyclopes always buy lenses in pairs.

For example 5 cyclopes with eyesight values [1,-1,2,3,-3] will need to buy 3 pairs of lenses.

I need to write a program that will count minimal amount of lens pairs need.

I tried it like this

int cyclops = 4;
int[] cyclopsSightValues = { 1, 7, 4, 1 };
if (cyclops < 2) { return 1;}
List<int> list = cyclopsSightValues .ToList();
int matchCount = 0;

for (int i = 0; i < list.Count; i++)
{
    for (int j = 0; j < list.Count; j++)
    {
        if (list[i] == list[j] ||
            list[i] + 1 == list[j] ||
            list[i] + 2 == list[j] ||
            list[i] - 1 == list[j] ||
            list[i] - 2 == list[j])
        {
            
            int valueToRemove1 = list[i];
            int valueToRemove2 = list[j];
            list.Remove(valueToRemove1);
            list.Remove(valueToRemove2);
            matchCount++;
           
            continue;
        }
    }
}
return matchCount + (cyclops-matchCount*2);

I think i need to find matching eyesights and remove them from list, but the result always comes out less then the correct one by 1. Maybe my logic is wrong altogether? Any help would be much appreciated.

Answer 1

Look, if two cyclops have eyesight difference 2 or less by absolute value they can buy lenses which fit both of them, e.g. 3 and 1 can buy pair of 2 lenses. Let's try to use greedy approach now: order cyclops by their eye sights and try to use spare lenses as frequent as we could:

1, -1, 2, 3, -3 -> -3, -1, 1, 2, 3

-3 v -1, 1 v 2, 3 
   can use
  -2       1   

So far so good all we have to do is to sort and scan:

private static int Solve(int[] cyclopsSightValues) {
  Array.Sort(cyclopsSightValues);

  int result = 0;
  bool hasSpare = false;

  for (int i = 0; i < cyclopsSightValues.Length; ++i)
    if (hasSpare && cyclopsSightValues[i - 1] + 2 >= cyclopsSightValues[i])
      hasSpare = false; // We use spare lense from the previous cyclope
    else {
      // we have to buy a pair, and now we have a spare lense 
      hasSpare = true;
      result += 1;
    }

  return result;
}

Demo:

int[][] tests = {
  new[] { 1, -1, 2, 3, -3 },
  new int[] { },
  new[] { 1, 1, 1, 1 },
};

string report = string.Join(Environment.NewLine, tests
  .Select(item => $"[{string.Join(", ", item)}] => {Solve(item)}"));

Console.Write(report);

Output:

[1, -1, 2, 3, -3] => 3
[] => 0
[1, 1, 1, 1] => 2

Please, fiddle yourself

Answer 2

Untested, but should more or less work:

public static IEnumerable<int> LensesToBuy(IEnumerable<int> cyclopsVisions)
{
    int? buf = null;
    var e = cyclopsVisions.OrderBy(v => v).GetEnumerator();
    while(e.MoveNext())
    {
        if (!buf.HasValue)
        {
            buf = e.Current;
        }
        else if (Math.Abs(buf.Value - e.Current) > 2) 
        { // cached value not compatible
            yield return buf.Value;
            buf = e.Current;
        }
        else
        {  // cached value is compatible
            if (buf.Value == e.Current) yield return buf.Value;
            if (buf.Value > e.Current) yield return buf.Value - 1;
            if (buf.Value < e.Current) yield return buf.Value + 1;
            buf = null;
        }                       
    } 
    if (buf.HasValue) yield return buf.Value;
}

Call it like this:

int[] cyclopsSightValues = { 1, 7, 4, 1 };

var result = LensesToBuy(cyclopsSightValues); //okay to pass array
Console.WriteLine(result.Count());