How to check if the sequence of ints has even and odd numbers alternating using LINQ, C#

user_13353974 0
Viewed 269

Let's say I have a list of ints in c# like this:

List<int> numbers = new List<int>() { 1, 2, 7, 20, 3 };

Is there a way of checking that it has alternating odd and even numbers in it (like in the example above: if one if them is even then the next must be odd or vice versa)?

I know it's simple to check it in a loop, but I'm trying to implement this using LINQ and extension methods only.

extension-methods algorithm linq c#
3 Answers

Let's analyze the problem. What does it mean alternating parity?

  index : value : value + index
  ------------------------------
      0 :     1 : 1 - note, all sums are odd
      1 :     2 : 3
      2 :     7 : 9
         ....

Or

  index : value : value + index
  ------------------------------
      0 :     2 : 2 - note, all sums are even
      1 :     1 : 2
      2 :     6 : 8
         ....

As you can see (and you can easily prove it) alternating parity means that index + value sums are either all odd or all even. Let's check it with a help of Linq:

  List<int> numbers = new List<int>() { 1, 2, 7, 20, 3, 79 };

  bool result = numbers
    .DefaultIfEmpty()
    .Select((item, index) => Math.Abs((long)item + (long)index))
    .Aggregate((s, a) => s % 2 == a % 2 ? s % 2 : -1) >= 0;

Notes to the implementation:

  1. DefaultIfEmpty() - empty sequence has all (all zero) values alternating; however, Aggregate has nothing to aggregate and throws exception. Let's turn empty sequence into one element sequence.
  2. (long) in order to prevent integer overflow (int.MaxValue + index can well be out of int range)
  3. Math.Abs: c# can return negative remainder (e.g. -1 % 2); we don't want an additional check for this, so let's work with absolute values
  4. However, we can exploit this effect (-1 % 2 == -1) in the final Aggregate

Extension Method solution I hope is easier to understand:

  public static bool IsAlternating(this IEnumerable<int> source) {
    if (null == source)
      throw new ArgumentNullException(nameof(source));

    bool expectedZero = false;
    bool first = true;

    foreach (int item in source) {
      int actual = item % 2;

      if (first) {
        first = false;
        expectedZero = actual == 0;
      } 
      else if (actual == 0 && !expectedZero || actual != 0 && expectedZero) 
        return false;  

      expectedZero = !expectedZero;
    } 

    return true;
  }

Note, that the loop solution (extension method) is more efficient: it returns false immediately when pattern doesn't meet.

user_23194070

You can do with LINQ in this way. you can check if there is atelast one even item at add place or an odd item at even place.

List<int> numbers = new List<int>() { 1, 2, 7, 20, 3 };
var temp = numbers.Where((x, i) => (i % 2 == 0 && x % 2 == 0) || (i % 2 == 1 && x % 2 == 1)).Take(1);
int count = temp.Count();
if(count == 0)
{
    //true
}
else
{
    //false
}

Note: Assuming that you are expecting even numbers at even place and odd numbers at an odd place.

user_65270490

You can use Aggregate to determine if a sequence is alternating.

Let's assume that if there's 0 or 1 elements then the result is true. You can modify this logic however you see fit.

Based on this an extension method can be created:

    public static bool IsAlternatingParitySequenceVerbose(this IEnumerable<int> col)
    {
        // state:
        // -1 - sequence is not alternating
        //  0 - even
        //  1 - odd

        if (!col.Any())
            return true;

        //check if first value is even
        var firstState = Math.Abs(col.First() % 2);

        var IsAlternating = col.Skip(1).Aggregate(firstState, (state, val) =>
        {
            if (state == -1)
                return -1;

            var current = Math.Abs(val % 2);
            if (current == state)
                return -1;

            return current;
        });

        return IsAlternating != -1;
    }

And then make a one-liner out of it:

    public static bool IsAlternatingParitySequence(this IEnumerable<int> col) =>
        !col.Any()
        || col.Skip(1).Aggregate(Math.Abs(col.First() % 2), (state, val) =>
                state == -1
                    ? -1
                    : Math.Abs(val % 2) is var current && current == state
                    ? -1
                    : current
            ) != -1;
user_80434740
Related