CODEWITHSUNDEEP
javaoop
roundar
roundar

Reputation: 1713

Determining if a list numbers are sequential

I'm working in Java. I have an unordered list of 5 numbers ranging from 0-100 with no repeats. I'd like to detect if 3 of the numbers are sequential with no gap.

Examples: 

[9,12,13,11,10] true
[17,1,2,3,5] true
[19,22,23,27,55] false

As for what I've tried, nothing yet. If I were to write it now, I would probably go with the most naive approach of ordering the numbers, then iteratively checking if a sequence exists.

Upvotes: 7

Views: 17163

Answers (7)

Pace
Pace

Reputation: 43817

Allocate an array of size 100:

private static final int MAX_VALUE = 100;

public boolean hasSequence(int [] values) {
  int [] bigArray = new int[MAX_VALUE];

  for(int i = 0; i < values.length; i++) {
    bigArray[values[i]] = 1;
  }

  for(int i = 0; i < values.length; i++) {
    index = values[i];
    if(index == 0 || index == MAX_VALUE-1) {
      continue;
    }
    if(bigArray[index-1] == 1 && bigArray[index+1] == 1) {
      return true;
    }
  }

  return false;
}

Upvotes: 1

Joop Eggen
Joop Eggen

Reputation: 109547

int sequenceMin(int[] set) {
    int[] arr = Arrays.copy(set);
    Arrays.sort(arr);
    for (int i = 0; i < arr.length - 3 + 1; ++i) {
        if (arr[i] == arr[i + 2] - 2) {
            return arr[i];
        }
    }
    return -1;
}

This sorts the array and looks for the desired sequence using the if-statement above, returning the first value.

Without sorting:

(@Pace mentioned the wish for non-sorting.) A limited range can use an efficient "boolean array", BitSet. The iteration with nextSetBit is fast.

    int[] arr = {9,12,13,11,10};
    BitSet numbers = new BitSet(101);
    for (int no : arr) {
        numbers.set(no);
    }
    int sequenceCount = 0;
    int last = -10;
    for (int i = numbers.nextSetBit(0); i >= 0; i = numbers.nextSetBit(i+1)) {
        if (sequenceCount == 0 || i - last > 1) {
            sequenceCount = 1;
        } else {
            sequenceCount++;
            if (sequenceCount >= 3) {
                System.out.println("Sequence start: " + (last - 1));
                break;
            }
        }
        last = i;
    }
    System.out.println("Done");

Upvotes: 3

Kelvin Ng
Kelvin Ng

Reputation: 174

Haven't test this, but for small memory footprint you could use a BitSet

private static boolean consecutive(int[] input) {
    BitSet bitSet = new BitSet(100);
    for (int num : input) {
        bitSet.set(num);
    }

    bitSet.and(bitSet.get(1, bitSet.length())); // AND shift left by 1 bit
    bitSet.and(bitSet.get(1, bitSet.length())); // AND shift left by 1 bit

    return !bitSet.isEmpty();
}

Upvotes: 0

Ajinkya
Ajinkya

Reputation: 22710

As OP pointed out in comment, he want to check if list contains 3 or more sequential numbers

public class WarRoom {

    static final int seqCount = 3;

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>((Arrays.asList(9, 11, 123, 511, 10)));
        for (int i : list) {
            if (seqNumbers(list, i, 0) >= seqCount) {
                System.out.println("Lucky Numbers : " + (i++) + "," + (i++) + "," + i);
            }
        }
    }

    public static int seqNumbers(List<Integer> list, int number, int count) {
        if (list.contains(number)) {
            return seqNumbers(list, number + 1, count + 1);
        }
        else {
            return count;
        }
    }
}

Its not one of the most efficient solution but I love recursion!

Upvotes: 0

Andrew_CS
Andrew_CS

Reputation: 2562

General Algorithm steps.

Step 1. Sort the array.
Step 2. There are only 3 possible groups of 3 (next to each other) in an array of length five.
indexes 0,1,2 - 1,2,3 - 2,3,4.
Step 3. Check these 3 combinations to see if the next index is 1 more than the current index.

Upvotes: 1

Adam Siemion
Adam Siemion

Reputation: 16039

This code seems to be implementing your requirements:

public class OrderdedList {
    public static void main(String[] args) {
        System.out.println(orderedWithNoGap(Arrays.asList(9, 12, 13, 11, 10))); // true
        System.out.println(orderedWithNoGap(Arrays.asList(17,1,2,3,5))); // true
        System.out.println(orderedWithNoGap(Arrays.asList(19,22,23,27,55))); // false
    }

    private static boolean orderedWithNoGap(List<Integer> list) {       
        Collections.sort(list);
        Integer prev = null;
        int seq = 0;
        for(Integer i : list) {
            if(prev != null && prev+1 == i)
                seq = seq == 0 ? 2 : seq+1;
            prev = i;
        }
        return seq >= 3;
    }

}

Upvotes: 3

Orab&#238;g
Orab&#238;g

Reputation: 11992

Very naive (but faster) algorithm : (your array is input[], assuming it only contains 0-100 numbers as you said)

int[] nums=new int[101];
for(i=0;i<N;i++) 
   {
   int a=input[i];
   nums[a]++;
   if (a>0) { nums[a-1]++; }
   if (a<100) { nums[a+1]++; }
   }

Then look if there is an element of nums[]==3.

Could be faster with some HashMap instead of the array (and removes the 0-100 limitation)

Edit : Alas, this does NOT work if two numbers could be equal in the initial sequence

Upvotes: 3

Related Questions