Check if array elements are consecutive without order

Question

I have the following code:

int[] arr = { 1, 2, 3, 4 };
int n = arr.Length;
bool result = areConsecutives(arr, n);
if (result == true)
    MessageBox.Show("Yes");
else
    MessageBox.Show("No"); 

static bool areConsecutives(int[] arr, int n)
{
    int first_term = int.MaxValue;

    for (int j = 0; j < n; j++)
    {
        if (arr[j] < first_term)
            first_term = arr[j];
    }

    int ap_sum = (n * (2 * first_term + (n - 1) * 1)) / 2;

    int arr_sum = 0;
    for (int i = 0; i < n; i++)
        arr_sum += arr[i];

    return ap_sum == arr_sum;
}

This works fine even if I change my array to this:

int[] arr = { 4, 2, 1, 3 }

The problem/question is what can I do to check if the array elements are consecutive, for example if I have the following array:

int[] arr = { 4, 8, 12, 16 }

They are consecutive/multiple by 4 and also the array can be in this way:

int[] arr = { 16, 4, 8, 12 }

What exactly do you mean by "consecutive"? That each element in the array is some other element plus a constant (except the lowest element)? — canton7
– canton7, Commented Feb 5, 2020 at 20:13
@canton7 By consecutive/multiple I mean for example 1, 2, 3, they are consecutive by 1. 3, 6, 9, 12, they are by 3 or, 75, 125, 150, 50, they are by 25, etc. — User1899289003
– User1899289003, Commented Feb 5, 2020 at 20:15
does "consecutive" means "we can re-order items such that we have an arithmetic progression", e.g. 3, 5, 11, 9, 7 can be put as 3, 5, 7, 9, 11? Or (more strict) "consecutive" means that all items can be represented as const * k where k = 1, 2, ..., n? — Dmitrii Bychenko
– Dmitrii Bychenko, Commented Feb 5, 2020 at 20:17
By "consecutive" do you mean the elements, when sorted, are evenly spaced? — John Wu
– John Wu, Commented Feb 5, 2020 at 20:18
@DmitryBychenko Yes, a way to do it maybe is to order the array elements from min and max and then check if they are consecutive/multiple of the difference between two first items, in your example the consecutive/multiple is 2. — User1899289003
– User1899289003, Commented Feb 5, 2020 at 20:19

canton7 · Accepted Answer · 2020-02-05 20:45:51Z

5

Here's one way:

var vals = new[] { 125, 25, 50, 75, 100 };
Array.Sort(vals);
bool arithmetic = vals.Zip(vals.Skip(1), (x, y) => y - x).Distinct().Count() == 1;

We start by sorting the array. Then we take each pair of elements (so take 25 and 50, then 50 and 75, etc) and find the difference between them. Then we take the number of different differences we found, and see if that's 1: if it is, our elements are evenly spaced.

Here's another:

var vals = new[] { 125, 50, 75, 100 };
Array.Sort(vals);
bool areArithmetic = true;
if (vals.Length > 1)
{
    int difference = vals[1] - vals[0]; 
    for (int i = 2; i < vals.Length; i++)
    {
        if (vals[i] != vals[0] + i * difference)
        {
            areArithmetic = false;
            break;
        }
    }
}

Here we sort the list again, and then loop through the sorted list. We find the difference between the first two elements, then check that every subsequent element is an appropriate multiple of that difference.

edited Feb 5, 2020 at 20:45

answered Feb 5, 2020 at 20:19

canton7

43.3k4 gold badges81 silver badges96 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

User1899289003 Over a year ago

This seems to work fine, but I'm not sure if this is going to work if I use negative or decimal numbers. For example int[] array = { 1.3, -1, 0. 1.5 }.

canton7 Over a year ago

{ 1.3, -1, 0, 1.5 } isn't an arithmetic progression... It should handle negative numbers, but floats are a tricky beast that are going to make any approach hard

canton7 · Accepted Answer · 2020-02-05 20:36:54Z

3

If you're not looking for an arithmetic progression and just simply want whether the numbers are consecutively growing then you could do something like this. Just check whether the previous value is ever greater than the current.

var isConsecutive = true;
var numbers = new[] { 1.3, -1, 0, 1.5 };
for (int i = 1; i < numbers.Length; i++)
{
    if (numbers[i - 1] > numbers[i])
    {
        isConsecutive = false;
        break;
    }
}

edited Feb 5, 2020 at 20:36

canton7

43.3k4 gold badges81 silver badges96 bronze badges

answered Feb 5, 2020 at 20:29

JSteward

7,1312 gold badges24 silver badges33 bronze badges

1 Comment

canton7 Over a year ago

@User1899289003 If this is actually the answer, you expressed your question very badly...

Pavel Anikhouski · Accepted Answer · 2020-04-29 18:59:55Z

1

A possible solution using Array.Sort and simple for loop, without System.Linq

int[] arr = { 16, 4, 8, 12 };
Array.Sort(arr);

bool result = true;
for (int i = 1; i < arr.Length - 1; i++)
    if (arr[i] - arr[i - 1] != arr[i + 1] - arr[i])
    {
        result = false;
        break;
    }

edited Apr 29, 2020 at 18:59

answered Feb 5, 2020 at 20:29

Pavel Anikhouski

23.6k12 gold badges66 silver badges81 bronze badges

Comments

Peter B · Accepted Answer · 2020-02-05 20:47:04Z

0

I would do it like this: determine which values are needed, and then check if arr contains each of those values.

var min = arr.Min(); // This is also the expected "gap" between elements
var max = min * arr.Length;
var isOK = min > 0;
for (var i = min; i <= max && isOK; i += min)
{
    if (!arr.Contains(i))
        isOK = false;
}
Console.WriteLine(isOK ? "Consecutive" : "Not consecutive");

Working demo: https://dotnetfiddle.net/YpSXwF

Or if 0 and negative values are also allowed:

var min = arr.Min();
var gap = arr.Where(x => x > min).Min() - min;
var max = min + gap * (arr.Length - 1);
var isOK = gap > 0;
for (var i = min; i <= max && isOK; i += gap)
{
    if (!arr.Contains(i))
        isOK = false;
}
Console.WriteLine(isOK ? "Consecutive" : "Not consecutive");

Working demo: https://dotnetfiddle.net/k3jGP5

edited Feb 5, 2020 at 20:47

answered Feb 5, 2020 at 20:28

Peter B

24.7k5 gold badges42 silver badges94 bronze badges

4 Comments

canton7 Over a year ago

You'd be better off using a HashSet, or linq's Except -- that will turn this from quadratic into linear

canton7 Over a year ago

Also note that the sequence might not have to start at its lowest value, necessarily, which your code assumes

Peter B Over a year ago

@canton7 HashSet can indeed be used as an optimization, but doing so does not change the logic (the algorithm) in any way. About your second comment: incorrect, if you try the demos then you will see that they use and work for any order of elements.

canton7 Over a year ago

Maybe I wasn't clear: I wasn't talking about the order of elements, I was talking about e.g. [4, 6, 8] (where here the sequence does not start at 2). You fixed this in your edit, though, by not assuming that the gap is the same as the minimum element.

Collectives™ on Stack Overflow

Check if array elements are consecutive without order

4 Answers 4

2 Comments

1 Comment

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

1 Comment

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related