CareerCup

I think one important thing to consider here is that array is sorted. We need to follow binary search approach here to have the complexity between O(logn) and O(n).
For the input given in the question, we have a sequence from a[0] to a[5]. We can find the sequence using the comparison (a[low]-a[high] == low-high)

A solution with binary search

public class FindSets {

	public static void main(String[] args) {
		int[] array = { 4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24,
				27 };
		int i = 0;
		int size = array.length;

		StringBuilder sb = new StringBuilder();
		while (i < size - 1) {

			int end = findEnd(i, size - 1, array);
			if (end != i) {
				sb.append("" + i + ":" + end);
				i = end + 1;
			} else
				i++;
		}
		System.out.println("O/P:" + sb.toString());
	}

	private static int findEnd(int i, int size, int[] array) {

		int low = i, high = size;
		int mid;

		while (low < high) {
			mid = (low + high) / 2;

			if (mid - low == array[mid] - array[low]) {
				if (mid - low + 1 < array[mid + 1] - array[low])
					return mid;
				else
					low = mid + 1;
			} else
				high = mid - 1;
		}
		return low;
	}

}

Note that the result could be stored in a variable that could be taken as a second parameter, that will avoid the copy of the results, however, for simplicity sake, thats not the case with the following code

bool isConsecutive(int first, int next){
  if (first >= next) return false;
  int difference = next - first;
  if (difference == 1)
	return true;
  return false;
}

vector<Range*> getRanges(const vector<int> &data){
  int start, end;
  vector<Range*> resutl;
  start = end = 0;
  size_t dataSize = data.size();
  if (size < 2 ) return;//a range must contain at least 2 numbers, start and end
  for (int i =0; i<dataSize -2; i++){ //0 based array with bounds check
  	int current = data[i];
        int next = data[i+1];
        if ( !isConsecutive(current, next) ) {
		end = i;//end current range secuende             
		if (start != end ) result.pushBack( new Range(start, end) );
                start = i;//reset starting point
             
       }//if
  }//for
return result;
}

// [4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27]
    private void accumulateSeqNos(int[] data){
        
        List<String> result = new ArrayList<String>();
        for(int i=0; i<data.length; i++){
            int head = data[i];
            while(i+1 < data.length){
                // Loop to find the range of consecutive
                if((data[i] + 1 != data[++i])){
                    i--;
                    break;
                }
            }
            if(head != data[i]){
                result.add("{" + head + " : " + data[i] + "}");
            }
        }
        
        for(int i=0; i<result.size(); i++){
            System.out.println(result.get(i));
        }
    }

public static void main(String[] args) {
int[] array = {4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};
int size = array.length;
boolean seq = false;
StringBuilder sb = new StringBuilder();
for(int i=0;i<size-1;i++){
if((array[i+1]- array[i])==1 && !seq){
sb.append("{"+array[i]+":");
seq = true;
}
if((array[i+1]- array[i])>1 && seq){
seq = false;
sb.append(""+array[i]+"}");
}

}
System.out.println("O/P:"+sb.toString());
}

O/P:{4:9}{15:18}{22:24}

public class SeqArraySet {
	
	public static void main(String[] args) {
		int[] array = {4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};
		int size = array.length;
		boolean seq = false;
		StringBuilder sb =  new StringBuilder();
		for(int i=0;i<size-1;i++){
			if((array[i+1]- array[i])==1 && !seq){
				sb.append("{"+array[i]+":");
				seq = true;
			}
			if((array[i+1]- array[i])>1 &&  seq){
				seq = false;					
				sb.append(""+array[i]+"}");
			}
			
		}
		System.out.println("O/P:"+sb.toString());
	}

}

O/P:{4:9}{15:18}{22:24}

I think using Skip Lists will give O(log n) time

I think using Skip Lists will give O(log n) time (under the assumption that the numbers in the array are unique). Skip every n/2 element and compare if the sequence has been broken

/**
 *
 * @author alikatkar
 */
public class RangeInArray {

    public class Range {

        private int begin;
        private int end;

        public Range(int begin, int end) {
            this.begin = begin;
            this.end = end;
        }

        @Override
        public String toString() {
            return "{" + begin + "," + end + '}';
        }
    }

    public List<Range> findRanges(int[] array) {
        
        List<Range> rangeList = new ArrayList<Range>();
        int i, j;
        for (i = 0; i < array.length; i = j + 1) {
            for (j = i; j < array.length - 1; j++) {
                if (array[j + 1] - array[j] == 1) {
                    continue;
                } else {
                    rangeList.add(new Range(array[i], array[j]));
                    break;
                }
            }
            if (j == array.length - 1) {
                rangeList.add(new Range(array[i], array[j]));
                break;
            }
        }
        return rangeList;
    }

    public static void main(String[] args) {

        int[] array = {4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};

        RangeInArray rangeInArray = new RangeInArray();
        List<Range> ranges = rangeInArray.findRanges(array);
        System.out.println(ranges);

    }
}

in Objective-C

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view, typically from a nib.
    NSArray *holder = @[@4, @5, @6, @7, @8, @9, @12, @15, @16, @17, @18, @20, @22, @23, @24, @27];
    [self getConNum:holder];
}

-(void)getConNum:(NSArray*)givenArray{
    BOOL isStart = YES;
    int start = 0;
    for(int i = 0; i < givenArray.count-1;i++){
        if([givenArray[i]intValue]==[givenArray[i+1]intValue]-1){
            if(isStart == YES ){
                start = [givenArray[i]intValue];
                isStart = NO;
            }
            
        }else if(isStart == NO){
            NSLog(@"Start:%d End:%d",start,[givenArray[i]intValue]);
            isStart = YES;
        }
    }
}

/**
 * @author Vlad Revkov
 */
public class ConsecNumbs {
	
	public static  void main (String[] args){
		int [] ar = {4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};
		consecNumbs(ar);
		
	}
	
	public static void consecNumbs( int [] ar){
		int indx = 0;
		
		for (int i=0; i <ar.length-1; i ++){
			if(ar[i+1] - ar[i] == 1 && indx == 0){
				System.out.print("{ " + ar[i]);
				indx ++;
			}
			
			else if (ar[i+1]- ar[i] > 1 && indx != 0){
				System.out.print(" : " + ar[i] + "}");
				indx = 0;			
			}
		}
	}
}

Out Put : { 4 : 9}{ 15 : 18}{ 22 : 24}

I could do it with O(N). Woundering if anyone could handle it within O(log N)
private final static int[] SEQUENCE = {4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};

public static void printSequenceList(int[] input) {
int start = input[0];
int end = -1;
int j = 1;
for( int i = 1; i < input.length; ++i) {
if( start == input[i] - j) {
j++;
} else {
if( j > 1) {
System.out.print(String.format("{%s:%s}", start, input[i-1]));
}
j = 1;
start = input[i];
}
}
System.out.println();
}

public class SequenceArray
{
static int[] arr={1,2,3,4,9,10,11,12,16,17,19,21,22,23};

public static void main(String[] args)
{
for(int i=0;i<arr.length;i++)
{
int k=checkSequence(i);
if(k!=0)
{
System.out.println(arr[i] +"-" +arr[i+k]);
i=i+k;
}
}

}

public static int checkSequence(int k)
{
int count=0;
for(int m=k;m<arr.length-1;m++)
{
if(arr[m+1]==arr[m]+1)
{
count++;
}
else
break;
}
return count;
}
}

#include <stdio.h>
int main(void){
int a[]={5,8,9,10,12,13,14,15,16,17,19,20,21};
int start[7];
int end[7];
int i,j,k,m,n;
i = j = k = m = n=0;

for (i=0;i<7;i++){
start[i] = 0;
end[i] = 0;
}
for (i=0;i<13;i++){
printf("%d ", a[i]);
}
i=0;
for (k=0; k < 13;k++) {
while ((a[k+1] - a[k]) == 1){
n++;
k++;
}
if (n > 0){
printf("n=%d k=%d a[k]=%d a[k-n]=%d and m=%d\n",n, k, a[k],a[k-n],m);
start[m]=k-n;
end[m]=k;
n = 0;
m++;
}
}
return 0;
}

public class SortedIndex {
public static void main(String[] args) {
	int[] a = {4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};
	List output = new ArrayList(), temp;
	int start = 0;
	int end = 0;
	int curr, prev;
	for(int i=1;i<a.length;i++){
		curr = a[i];
		prev = a[i-1];
		if((curr-prev) == 1){
			end = i;
		}else{
			temp = new ArrayList();
			temp.add(start);
			temp.add(end);
			output.add(temp);
			start = (i+1);
			end = (i+1);
		}
		//System.out.println(a[i]);
	}
	System.out.println(output);
	
}
}

private static Iterable<Integer> findRanges(int[] sorted) {
		if (sorted.length == 0) {
			return Collections.<Integer> emptyList();
		}
		int end = sorted.length - 1;
		ArrayList<Integer> boundaries = new ArrayList<>();
		boundaries.add(0);
		findRanges(sorted, 0, end, boundaries);
		boundaries.add(end);
		return boundaries;
	}

	private static void findRanges(int[] sorted, int start, int end,
			List<Integer> boundaries) {
		if (start >= end || sorted[end] - sorted[start] == end - start) {
			return;
		}

		int midIdx = (start + end) / 2;
		findRanges(sorted, start, midIdx - 1, boundaries);

		if (midIdx - 1 >= start && sorted[midIdx] - sorted[midIdx - 1] > 1) {
			boundaries.add(midIdx - 1);
			boundaries.add(midIdx);
		}

		if (midIdx + 1 <= end && sorted[midIdx + 1] - sorted[midIdx] > 1) {
			boundaries.add(midIdx);
			boundaries.add(midIdx + 1);
		}

		findRanges(sorted, midIdx + 1, end, boundaries);
	}

Best case: O(1)
Worst case: O(N)

public List<Range> findRanges(int[] a){
        List<Range> list = new ArrayList<Range>();
        int start = 0;
        int end = 0;
        int i = 0;
        while(i < a.length){
            while((i < a.length-1) && (a[i]+1 == a[i+1])){
                end++;
                i++;
            } 
            list.add(new Range(a[start], a[end]));
            if(i < a.length-1){
                start = i+1;
                end = i+1;
            }
            i++;
        }
        
        return list;
    }

c code


int a[] = {1,3,4,7,8,9,10,12};
void rec(int *a,int *l ,int * r)
{
int mid =0;
if((a[*r] - a[*l]) == (*r -*l))
{
printf(" complete sequence left %d to right %d\n",*l,*r);
return;
}
else
{
if( (*r - *l) == 1)
{
printf(" sequence break left index %d to right index %d left elem %d right elem %d\n",*l,*r,a[*l],a[*r]);
return;
}
mid = (*l + *r)/2;
rec(a,l,&mid);
rec(a,&mid,r);





}


}



int main(int argc, char **argv)
{
int l =0;
int r =7;
rec(a,&l,&r);
return 0;
}

Using the binary search approach this solution will output all the sequences in an array. I wrote it in LINQPad so it's not too elegant, but does work .. also I output the values into a Dictionary as am not sure what they mean to output in a list (since each entry would need to be start and end index):

void Main()
{	
	
	int[] nums=new int[]{4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};
	
	Dictionary<int,int> dict=new Dictionary<int,int>();
	FindSequence(nums,dict,0);
	
	dict.Dump();
	 	
}

private static void FindSequence(int[] nums,Dictionary<int,int> dict,int seqStart)
{
	int mid, first = seqStart, last = nums.Length - 1;
	
	bool found = false;
	 
	int lastMatchIndex=-1;
	while (!found && first<=last)
    {
        mid = (first + last) / 2;

        if (nums[seqStart]+mid-seqStart == nums[mid])
        {
            first = mid + 1;
			lastMatchIndex=mid;			
        }
       	else if(nums[seqStart]+mid != nums[mid])
        {
            last = mid - 1;
        }				
    }
	
	if(lastMatchIndex!=-1)
	{
		dict[seqStart]=lastMatchIndex;
	}
	
	if(lastMatchIndex!=-1 && lastMatchIndex<nums.Length-1)
	{
		FindSequence(nums,dict,lastMatchIndex+1);
	}
		
}

here is my solution::

public static void printRanges(int[] arr){
		int i,j;
		for(i=0;i<arr.length;i=j+1){
			for(j=i;j<arr.length-1;j++){
				if(arr[j+1] - arr[j] == 1){
					continue;
				}else{
					
					//print range from i to j
					for(int k=i;k<=j;k++){
						System.out.print(arr[k]);
					}
					
					System.out.println(" ");
					break;
					
				}
			}
			
			if(j == arr.length-1){
				//print range from i to j
				for(int k=i;k<=j;k++){
					System.out.print(arr[k]);
				}
				break;
			}
		}
		
	}

import java.util.ArrayList;
import java.util.List;

public class FindNumberSequence {

	public static void main(String[] args) {
		//input number sequence
		int[] nos = {4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};

		//A list to hold all start and end index combination
		List<Index> allIndices = new ArrayList<>();
		
		//initialize the start and end index
		int sIndex = -1, eIndex = -1;

		//index points to current array element
		int i = 0;
		
		while(i < nos.length){
		    //index points to next array element to the current
			int j = i + 1;
			
			//Have we reached end of array?
			if(j >= nos.length) {
				if(sIndex > -1 && eIndex > -1){
					Index aIndex = new Index(sIndex, eIndex);
					allIndices.add(aIndex);
					sIndex = -1;
					eIndex = 1;
				}
				break;
			}
			
			//get the current element value and + 1, them compare it with
			//next element
			if(nos[i] + 1 == nos[j]){
				
				//if start index is not initialized, do it
				if(sIndex == -1){
					sIndex = i;
				}
				
				//update the end index
				eIndex = j;
			} else {
				//if current and next element are not of diff 1, then create the index obj 
				//and store in list
				if(sIndex > -1 && eIndex > -1){
					Index aIndex = new Index(sIndex, eIndex);
					allIndices.add(aIndex);
					sIndex = -1;
					eIndex = 1;
				}
			}
			
			i++;
		}
		
		for(Index ind: allIndices){
			System.out.println(ind);
		}
	}
	
	static class Index{
		private int start;
		private int end;
		private int[] consecutiveNumbers;
		
		Index(int s, int e){
			start = s;
			end = e;
		}
		
		public int getStart() {
			return start;
		}
		public void setStart(int start) {
			this.start = start;
		}
		public int getEnd() {
			return end;
		}
		public void setEnd(int end) {
			this.end = end;
		}
		public int[] getConsecutiveNumbers() {
			return consecutiveNumbers;
		}
		public void setConsecutiveNumbers(int[] consecutiveNumbers) {
			this.consecutiveNumbers = consecutiveNumbers;
		}
		
		public String toString(){
			return "Sequence Starts at: " + start + " and ends at: " + end;
		}
	}

}