Google Interview Question
iOS DevelopersCountry: United States
Interview Type: Phone Interview
public class Range
{
int start;
int end;
Range(int s, int e)
{
start=s;
end=e;
}
}
public class ArraySvc
{
public static ArrayList<Range> findConsecSegments(int[] a) throws NullPointerException, InvalidInputException
{
if(a==null)
{
throw new NullPointerException();
}
if(a.length==0)
{
throw InvalidInputException();
}
ArrayList<Range> results=new ArrayList<Range>();
Range r=new Range(a[0],a[0]);
for(int i=1;i<a.length;i++)
{
if(a[i]-a[i-1]!=1)
{
r.end=a[i-1];
results.add(r);
r=new Range(a[i],a[i]);
}
}
results.insert(r);
return results;
}
private static int[] getTestArray(int n)
{
if(n<=0)
{
return null;
}
Random rnd=new Random();
int[] arr=new int[n];
for(int i=0;i<n;i++)
{
arr[i]=rnd.nextInt(arr.length()*20);
}
Arrays.sort(arr);
return arr;
}
public static void main(String[] args)
{
Random rnd=new Random();
int[] arr=ArraySvc.getTestArray(rnd.nextInt(1001));
System.out.println(Arrays.toString(arr));
ArrayList<Integer> results=ArraySvc.findConsecSegments(arr);
for(Range r: results)
{
System.out.println("start: " + r.start + "end: " + r.end);
}
}
}
O(n) time complexity, O(n) space complexity (worst case is when none of the integers are consecutive).
O(n) with O(1) memory:
public static void numberCompression(int[] arr){
if(arr == null){
throw new NullPointerException();
}
if(arr.length == 0){
return;
}
int lastNumber = arr[0];
Integer rangeStart = lastNumber;
StringBuilder output = new StringBuilder();
for(int i = 1; i < arr.length; i++){
if(rangeStart == null){
rangeStart = arr[i];
}
else if(arr[i] -1 != lastNumber){
printOutput(rangeStart, lastNumber);
rangeStart = null;
}
lastNumber = arr[i];
}
if(rangeStart != null){
printOutput(rangeStart, lastNumber);
}
}
private static void printOutput(Integer rangeStart, int lastNumber){
if(rangeStart != lastNumber){
java.lang.System.out.println(rangeStart+" - "+lastNumber);
}
else{
java.lang.System.out.println(rangeStart);
}
}
list = [1,2,3,10,25,26,30,31,32,33]
seg = ''
seq = 'no' # by default assume the number is not sequenced
for i in range (len(list)-1):
if seq =='no':
first = list[i]
if list[i+1] - list[i] == 1:
seq = 'yes'
if i + 1 == len(list) - 1:
seg = seg + str(first) + '-' + str(list[i+1])
print seg
else:
continue
if list[i+1] - list[i] != 1:
if seq == 'yes':
seg = seg + str(first) + '-' + str(list[i]) + ','
seq = 'no'
else:
seg = seg + str(list[i]) + ','
seq = 'no'
#include<stdio.h>
#include<stdlib.h>
void consecutive(int *arr){
int i,j=0;
for (i=0;i<10;i++){
if (j==0){
printf("%d",arr[i]);
}
if (arr[i+1]-arr[i] == 1){
j = 1;
}
else{
if (j!=0){
printf("-%d\t",arr[i]);
}
else{
printf("\t");
}
j =0;
}
}
printf("\n");
}
int main(){
int arr[] = {1,2,3,10,25,26,30,31,32,33};
int i;
consecutive(arr);
return 0;
}
import java.util.List;
import java.util.ArrayList;
public class FindConsecutiveRanges{
public List<String> findConsecutiveRanges(int [] arr){
if(arr == null || arr.length == 0){
return null;
}
int startIndex = 0;
int n = arr[startIndex];
List<String> results = new ArrayList<String>();
for(int i = 1; i < arr.length; i++){
if(arr[i] != n + 1){
if(i - startIndex < 2){
results.add(n + "");
}else{
results.add(arr[startIndex] + " - " + n);
}
startIndex = i;
}
n = arr[i];
}
if(arr[startIndex] != arr[arr.length - 1]){
results.add(arr[startIndex] + " - " + n);
}else{
results.add(n + "");
}
return results;
}
public static void main(String[] args) {
FindConsecutiveRanges f = new FindConsecutiveRanges();
int [] arr = {1, 2, 3, 7, 11, 21};
System.out.println(f.findConsecutiveRanges(arr));
}
}
public class ConsecutiveSegments {
public void print(int [] array) {
if (array == null || array.length == 0) {
System.out.println("Nothing to print!");
} else if (array.length == 1) {
System.out.println(array[0]);
} else {
boolean consecutive = false;
for (int i = 1; i < array.length; ++i) {
if (array[i] != array[i - 1] + 1) {
if (consecutive) {
System.out.print("-");
}
System.out.print(array[i - 1] + ", ");
consecutive = false;
} else if (!consecutive) {
consecutive = true;
System.out.print(array[i - 1]);
}
}
if (consecutive) {
System.out.print("-");
}
System.out.print(array[array.length - 1]);
}
}
}
O(N) time, O(1) space
public static void showConsecutiveNumbers(int[] arr) {
int arrLen = arr.length;
int start = 0;
int end = 0;
while (end < arrLen) {
if (!(end == arrLen - 1) && (arr[end] + 1 == arr[end + 1])) {
end++;
} else {
if (start != end) {
System.out.print(arr[start] + " - " + arr[end] + " ,");
} else {
System.out.print(arr[start] + " ,");
}
start = end;
start++;
end++;
}
}
}
public static void showConsecutiveNumbers(int[] arr) {
int arrLen = arr.length;
int start = 0;
int end = 0;
while (end < arrLen) {
if (!(end == arrLen - 1) && (arr[end] + 1 == arr[end + 1])) {
end++;
} else {
if (start != end) {
System.out.print(arr[start] + " - " + arr[end] + " ,");
} else {
System.out.print(arr[start] + " ,");
}
start = end;
start++;
end++;
}
}
}
public class ListCompression {
public static void compressList(List<Integer> input) {
for (int i = 0; i < input.size(); ++i) {
int j = i;
while (j + 1 < input.size() && input.get(j + 1) - input.get(j) <= 1) j++;
if (input.get(j) != input.get(i))
System.out.print(input.get(i) + "-" + input.get(j) + ",");
else
System.out.print(input.get(i) + ",");
i = j;
}
}
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(10);
list.add(25);
list.add(26);
list.add(30);
list.add(31);
list.add(32);
list.add(33);
compressList(list);
}
}
import java.io.*;
class GFG {
public static void main (String[] args) {
//code
int [] a={-1,1, 2, 3,10, 25, 26, 30, 31, 32, 33,40};
int first=0;
int last=0,count=1;
System.out.println(a.length);
for(int i=0;i<a.length-1;i++){
if(a[i+1]==a[i]+1){
last=i+1;
count++;
}
else{
if(count>1)
System.out.print(a[first]+"-"+a[last]+",");
else if(count==1)
System.out.print(a[first]+",");
first=i+1;
count=1;
}
}
if(count>1)
System.out.print(a[first]+"-"+a[last]);
else if(count==1)
System.out.print(a[first]);
//output: 1-3, 10, 25-26, 30-33
}
}
import java.io.*;
class GFG {
public static void main (String[] args) {
//code
int [] a={-1,1, 2, 3,10, 25, 26, 30, 31, 32, 33,40};
int first=0;
int last=0,count=1;
System.out.println(a.length);
for(int i=0;i<a.length-1;i++){
if(a[i+1]==a[i]+1){
last=i+1;
count++;
}
else{
if(count>1)
System.out.print(a[first]+"-"+a[last]+",");
else if(count==1)
System.out.print(a[first]+",");
first=i+1;
count=1;
}
}
if(count>1)
System.out.print(a[first]+"-"+a[last]);
else if(count==1)
System.out.print(a[first]);
//output: 1-3, 10, 25-26, 30-33
}
}
import java.io.*;
class GFG {
public static void main (String[] args) {
//code
int [] a={-1,1, 2, 3,10, 25, 26, 30, 31, 32, 33,40};
int first=0;
int last=0,count=1;
System.out.println(a.length);
for(int i=0;i<a.length-1;i++){
if(a[i+1]==a[i]+1){
last=i+1;
count++;
}
else{
if(count>1)
System.out.print(a[first]+"-"+a[last]+",");
else if(count==1)
System.out.print(a[first]+",");
first=i+1;
count=1;
}
}
if(count>1)
System.out.print(a[first]+"-"+a[last]);
else if(count==1)
System.out.print(a[first]);
//output: 1-3, 10, 25-26, 30-33
}
}
vector<string> numbersegments(vector<long>& data)
{
ostringstream oss;
vector<string> result;
oss << data.front();
for (vector<long>::iterator it = data.begin(); it != data.end(); it++)
{
if (it == (data.end() - 1) || *it != (*(it + 1) - 1))
{
if (!oss.str().empty())
oss << '-';
oss << *it;
result.push_back(oss.str());
oss.str("");
} else if (oss.str().empty())
oss << *it;
}
return result;
}
void PrintCompList(int a[], int len)
{
int r = 0, start = 0;
while (r < (len-1)) {
while (a[r+1] == (a[r] + 1)) {
if (start == 0) {
cout << a[r] << "-";
start = 1;
}
++r;
};
cout << a[r++] << ",";
start = 0;
};
//cout << len << ":" << r << endl;
if(r < len) { cout << a[r] << endl; }
}
int main()
{
int arr[] = { 1, 2, 3, 10, 25, 26, 30, 31, 32, 33, 34, 76, 84, 85};
size_t len = sizeof(arr)/sizeof(int);
PrintCompList(arr, len);
return(0);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
ArrayList<Integer> myList = new ArrayList<Integer>();
String s = scanner.nextLine();
String[] items = s.split("[, ]+");
for (int i = 0; i < items.length; i++)
{
myList.add(new Integer(Integer.parseInt(items[i])));
}
int left = 0;
int right = 0;
boolean result = false;
while (left < myList.size())
{
while (right < myList.size() - 1 &&
myList.get(right + 1).intValue() ==
myList.get(right).intValue() + 1)
{
right++;
}
if (result)
{
System.out.print(", ");
}
if (right > left)
{
System.out.print("" + myList.get(left) + "-" + myList.get(right));
}
else
{
System.out.print("" + myList.get(left));
}
result = true;
left = right = right + 1;
}
System.out.println();
}
public class ConsecutiveMain {
public static void main(String[] args){
int[] array = {1,2,3,10,25,26,30,31,32,33};
int j=1;
int i =0;
String out = String.valueOf(array[i]);
String result = "";
while(j<array.length){
if(array[j] == array[i]+1 && j < array.length-1){
out = out + "-" +String.valueOf(array[j]);
}
else{
result = result + out + ",";
out = String.valueOf(array[j]);
}
i++;
j++;
}
if(j == array.length){
System.out.println(result);
}
}
#include <stdio.h>
void func(int a[], int n){
int i =1, var, store;
for (i=1; i < n; i++) {
var = a[i-1];
store = var;
while(a[i] == var+1 || a[i] == var) {
var = a[i];
i++;
}
while (var >= store)
printf("subset: %d\t", store++);
printf("\n");
}
return;
}
int main(){
int i,n = 0;
int a[]={1,2,2,3,10,25,26,30,31,32,33};
n = sizeof(a)/sizeof(a[0]);
func(a,n);
printf("original array:");
for (i=0; i<n ; i++)
printf("%d\t", a[i]);
printf("\n");
return 0;
}
#include <stdio.h>
void func(int a[], int n){
int i =1, var, store;
for (i=1; i < n; i++) {
var = a[i-1];
store = var;
while(a[i] == var+1 || a[i] == var) {
var = a[i];
i++;
}
while (var >= store)
printf("subset: %d\t", store++);
printf("\n");
}
return;
}
int main(){
int i,n = 0;
int a[]={1,2,2,3,10,25,26,30,31,32,33};
n = sizeof(a)/sizeof(a[0]);
func(a,n);
printf("original array:");
for (i=0; i<n ; i++)
printf("%d\t", a[i]);
printf("\n");
return 0;
}
#include <stdio.h>
void func(int a[], int n){
int i =1, var, store;
for (i=1; i < n; i++) {
var = a[i-1];
store = var;
while(a[i] == var+1 || a[i] == var) {
var = a[i];
i++;
}
while (var >= store)
printf("subset: %d\t", store++);
printf("\n");
}
return;
}
int main(){
int i,n = 0;
int a[]={1,2,2,3,10,25,26,30,31,32,33};
n = sizeof(a)/sizeof(a[0]);
func(a,n);
printf("original array:");
for (i=0; i<n ; i++)
printf("%d\t", a[i]);
printf("\n");
return 0;
}
#include <stdio.h>
void func(int a[], int n){
int i =1, var, store;
for (i=1; i < n; i++) {
var = a[i-1];
store = var;
while(a[i] == var+1 || a[i] == var) {
var = a[i];
i++;
}
while (var >= store)
printf("subset: %d\t", store++);
printf("\n");
}
return;
}
int main(){
int i,n = 0;
int a[]={1,2,2,3,10,25,26,30,31,32,33};
n = sizeof(a)/sizeof(a[0]);
func(a,n);
printf("original array:");
for (i=0; i<n ; i++)
printf("%d\t", a[i]);
printf("\n");
return 0;
}
public static void main(String[] args) {
int x[]={1,2,3,10,25,26,30,31,32,33,45,46,47};
int i=0;
System.out.println(" Length "+x.length);
while(i<x.length)
{
int t1=x[i];
int t2=t1;
while((i<x.length)&&(t2==x[i]))
{
t2++;
i++;
}
int finalValue=t2-1;
if(finalValue==t1)
{System.out.print(t1);System.out.print(" ,");}
else
{System.out.print(t1+"-"+finalValue);System.out.print(" ,");}
}
}
public static void compress(int a[])
{
int start = a[0], end = a[0];
for(int i = 1; i < a.length; i++)
{
if(a[i] - a[i - 1] != 1)
{
end = a[i - 1];
if(end != start)
System.out.println(start + "-" + end + ", ");
else
System.out.println(start + ", ");
start = a[i];
if(i == a.length - 1)
{
System.out.println(a[i]);
}
}
else if(a[i] - a[i - 1] == 1 && i == a.length - 1)
{
end = a[i];
if(end != start)
System.out.println(start + "-" + end);
}
}
}
def find_ranges(l):
ranges = []
cur_start = -1
cur_end = -1
if not l:
raise Exception("Empty list")
cur_start = l[0]
for i in xrange(1, len(l)):
if l[i] != l[i-1] + 1:
cur_end = l[ i- 1]
ranges.append((cur_start, cur_end))
cur_start = l[i]
ranges.append((cur_start,l[-1]))
result = format_ranges(ranges)
return result
def format_ranges(ranges):
result = []
for r in ranges:
if r[0] == r[1]:
result.append(str(r[0]))
else:
result.append(str(r[0]) + '-' + str(r[1]))
return result
l = [1,2,3,10,25,26,30,31,32,33]
print find_ranges(l)
static string compress(int[] a)
{
var sb = new StringBuilder();
sb.Append(a[0]);
for (int i = 1; i < a.Length; i++)
{
if (i < a.Length - 1 && a[i] == a[i - 1] + 1 && a[i] == a[i + 1] - 1)
{
if (sb[sb.Length - 1] != '-')
sb.Append("-");
continue;
}
else
{
if (sb[sb.Length - 1] != '-')
sb.Append(",");
sb.Append(a[i]);
}
}
return sb.ToString();
}
class Solution {
public static class Test {
public void run(int[] data) {
if (data == null || data.length == 0) return;
int first = data[0];
for (int i=1; i<data.length; i++) {
if (data[i-1] != data[i] && data[i] != data[i-1] + 1) {
print(data, i, first);
first = data[i];
}
}
//print the last range
print(data, data.length, first);
System.out.println();
}
private void print(int[] data, int pos, int first) {
if (first != data[pos-1]) { //range
System.out.print(" " + first + "-" + data[pos-1]);
} else { //single item
System.out.print(" " + first);
}
}
}
public static void main(String[] args) {
new Test().run(new int[]{});
new Test().run(new int[]{10});
new Test().run(new int[]{1, 2, 3, 10, 11, 14, 16, 17});
new Test().run(new int[]{1, 2, 3, 10, 11, 14, 16, 17, 20});
new Test().run(new int[]{1, 2, 3, 10, 11, 11, 14, 16, 17, 20});
new Test().run(new int[]{1, 2, 2, 3, 10, 11, 11, 14, 16, 17, 20, 20});
}
}
/*
Result:
10
1-3 10-11 14 16-17
1-3 10-11 14 16-17 20
1-3 10-11 14 16-17 20
1-3 10-11 14 16-17 20
*/
class Solution {
public static class Test {
public void run(int[] data) {
if (data == null || data.length == 0) return;
int first = data[0];
for (int i=1; i<data.length; i++) {
if (data[i-1] != data[i] && data[i] != data[i-1] + 1) {
print(data, i, first);
first = data[i];
}
}
//print the last range
print(data, data.length, first);
System.out.println();
}
private void print(int[] data, int pos, int first) {
if (first != data[pos-1]) { //range
System.out.print(" " + first + "-" + data[pos-1]);
} else { //single item
System.out.print(" " + first);
}
}
}
public static void main(String[] args) {
new Test().run(new int[]{});
new Test().run(new int[]{10});
new Test().run(new int[]{1, 2, 3, 10, 11, 14, 16, 17});
new Test().run(new int[]{1, 2, 3, 10, 11, 14, 16, 17, 20});
new Test().run(new int[]{1, 2, 3, 10, 11, 11, 14, 16, 17, 20});
new Test().run(new int[]{1, 2, 2, 3, 10, 11, 11, 14, 16, 17, 20, 20});
}
}
----------
10
1-3 10-11 14 16-17
1-3 10-11 14 16-17 20
1-3 10-11 14 16-17 20
1-3 10-11 14 16-17 20
class Solution {
public static class Test {
public void run(int[] data) {
if (data == null || data.length == 0) return;
int first = data[0];
for (int i=1; i<data.length; i++) {
if (data[i-1] != data[i] && data[i] != data[i-1] + 1) {
print(data, i, first);
first = data[i];
}
}
//print the last range
print(data, data.length, first);
System.out.println();
}
private void print(int[] data, int pos, int first) {
if (first != data[pos-1]) { //range
System.out.print(" " + first + "-" + data[pos-1]);
} else { //single item
System.out.print(" " + first);
}
}
}
public static void main(String[] args) {
new Test().run(new int[]{});
new Test().run(new int[]{10});
new Test().run(new int[]{1, 2, 3, 10, 11, 14, 16, 17});
new Test().run(new int[]{1, 2, 3, 10, 11, 14, 16, 17, 20});
new Test().run(new int[]{1, 2, 3, 10, 11, 11, 14, 16, 17, 20});
new Test().run(new int[]{1, 2, 2, 3, 10, 11, 11, 14, 16, 17, 20, 20});
}
}
/*
10
1-3 10-11 14 16-17
1-3 10-11 14 16-17 20
1-3 10-11 14 16-17 20
1-3 10-11 14 16-17 20
*/
class Solution {
public static class Test {
public void run(int[] data) {
if (data == null || data.length == 0) return;
int first = data[0];
for (int i=1; i<data.length; i++) {
if (data[i-1] != data[i] && data[i] != data[i-1] + 1) {
print(data, i, first);
first = data[i];
}
}
//print the last range
print(data, data.length, first);
System.out.println();
}
private void print(int[] data, int pos, int first) {
if (first != data[pos-1]) { //range
System.out.print(" " + first + "-" + data[pos-1]);
} else { //single item
System.out.print(" " + first);
}
}
}
public static void main(String[] args) {
new Test().run(new int[]{});
new Test().run(new int[]{10});
new Test().run(new int[]{1, 2, 3, 10, 11, 14, 16, 17});
new Test().run(new int[]{1, 2, 3, 10, 11, 14, 16, 17, 20});
new Test().run(new int[]{1, 2, 3, 10, 11, 11, 14, 16, 17, 20});
new Test().run(new int[]{1, 2, 2, 3, 10, 11, 11, 14, 16, 17, 20, 20});
}
}
/*
10
1-3 10-11 14 16-17
1-3 10-11 14 16-17 20
1-3 10-11 14 16-17 20
1-3 10-11 14 16-17 20
*/
class Solution {
public static class Test {
public void run(int[] data) {
if (data == null || data.length == 0) return;
int first = data[0];
for (int i=1; i<data.length; i++) {
if (data[i-1] != data[i] && data[i] != data[i-1] + 1) {
print(data, i, first);
first = data[i];
}
}
//print the last range
print(data, data.length, first);
System.out.println();
}
private void print(int[] data, int pos, int first) {
if (first != data[pos-1]) { //range
System.out.print(" " + first + "-" + data[pos-1]);
} else { //single item
System.out.print(" " + first);
}
}
}
public static void main(String[] args) {
new Test().run(new int[]{});
new Test().run(new int[]{10});
new Test().run(new int[]{1, 2, 3, 10, 11, 14, 16, 17});
new Test().run(new int[]{1, 2, 3, 10, 11, 14, 16, 17, 20});
new Test().run(new int[]{1, 2, 3, 10, 11, 11, 14, 16, 17, 20});
new Test().run(new int[]{1, 2, 2, 3, 10, 11, 11, 14, 16, 17, 20, 20});
}
}
/*
10
1-3 10-11 14 16-17
1-3 10-11 14 16-17 20
1-3 10-11 14 16-17 20
1-3 10-11 14 16-17 20
*/
Objective-C
+(NSString *)findConsecutiveSegmentsOfArray: (NSArray *) array{
NSMutableString *arrayElements = [[NSMutableString alloc] init];
BOOL isConsecutive = NO;
for (NSUInteger i=0; i<array.count; i++) {
NSUInteger number = [array[i]integerValue];
if (i == array.count-1) {
[arrayElements appendString:[NSString stringWithFormat:@"%lu",number]];
return arrayElements;
}
NSUInteger adjacentNumber = [array[i+1] integerValue];
if (number +1 == adjacentNumber) {
if(isConsecutive){
continue;
}
else {
[arrayElements appendString:[NSString stringWithFormat:@"%lu-",(unsigned long)number]];
isConsecutive = YES;
}
}
else {
[arrayElements appendString:[NSString stringWithFormat:@"%lu, ", (unsigned long)number]];
isConsecutive =NO;
}
}
return nil;
}
Objective C
+(NSString *)findConsecutiveSegmentsOfArray: (NSArray *) array{
NSMutableString *arrayElements = [[NSMutableString alloc] init];
BOOL isConsecutive = NO;
for (NSUInteger i=0; i<array.count; i++) {
NSUInteger number = [array[i]integerValue];
if (i == array.count-1) {
[arrayElements appendString:[NSString stringWithFormat:@"%lu",number]];
return arrayElements;
}
NSUInteger adjacentNumber = [array[i+1] integerValue];
if (number +1 == adjacentNumber) {
if(isConsecutive){
continue;
}
else {
[arrayElements appendString:[NSString stringWithFormat:@"%lu-",(unsigned long)number]];
isConsecutive = YES;
}
}
else {
[arrayElements appendString:[NSString stringWithFormat:@"%lu, ", (unsigned long)number]];
isConsecutive =NO;
}
}
return nil;
}
mas=[]
mas1=[]
def fnext(sm,index):
if index+1<len(sm):
if sm[index+1]-sm[index]==1:
mas.append(sm[index+1])
mas1.append(sm[index+1])
fnext(sm,index+1)
return mas
def find(sm):
global mas
cm=[]
potential_el=0
for i in range(len(sm)):
if sm[i] not in mas1:
mas.append(sm[i])
mas1.append(sm[i])
fnext(sm,i)
cm.append(mas)
mas=[]
else:
continue
return(cm)
def printing(cm):
cmf=[]
st=""
for i in cm:
st+=str(i[0])
if len(i)<2:
cmf.append(st)
if len(i)>1:
st+="-"+str(i[-1])
cmf.append(st)
st=st.replace(st,"")
return cmf
print(printing(find([1,2,3,10,25,26,30,31,32,33])))
output:
['1-3', '10', '25-26', '30-33']
// Option 1
- (void)consecutiveSequences:(NSArray *)array
{
NSRange range = NSMakeRange([[array objectAtIndex:0] integerValue], 0);
for(int i = 1; i < array.count; i++) {
if(range.location + range.length + 1 != [[array objectAtIndex:i] integerValue]) {
if(range.length > 0)
NSLog(@"%d-%d", (int)range.location, (int)range.location + (int)range.length);
else
NSLog(@"%d", (int)range.location);
range = NSMakeRange([[array objectAtIndex:i] integerValue], 0);
}
else {
range = NSMakeRange(range.location, range.length + 1);
}
}
if(range.length > 0)
NSLog(@"%d-%d", (int)range.location, (int)range.location + (int)range.length);
else
NSLog(@"%d", (int)range.location);
}
// Option 2
- (void)consecutiveSequences:(NSArray *)array
{
NSInteger first = INT_MIN;
NSInteger last = INT_MIN;
BOOL initiated = false;
for(int i = 0; i < array.count; i++) {
if(initiated == false) {
first = [[array objectAtIndex:i] integerValue];
last = [[array objectAtIndex:i] integerValue];
initiated = true;
}
else if(last + 1 != [[array objectAtIndex:i] integerValue]) {
if(first != last)
NSLog(@"%d-%d", (int)first, (int)last);
else
NSLog(@"%d", (int)first);
first = [[array objectAtIndex:i] integerValue];
last = [[array objectAtIndex:i] integerValue];
}
else {
last = [[array objectAtIndex:i] integerValue];
}
}
if(first != last)
NSLog(@"%d-%d", (int)first, (int)last);
else
NSLog(@"%d", (int)first);
}
void PrintConsecutiveNumbers (int * array, int size) {
int i = 0; int j;
bool cont;
int start = array[0];
while (i < size) {
printf("%i",start);
cont = true;
for (j = 1; cont; j++) {
int nxtSeq = array[i+j];
if ((start+j)!=nxtSeq) {
cont = false;
if(j!=1) {
printf("-%i\n",array[i+j-1]);
} else {
printf("\n");
}
start = nxtSeq;
i+=j;
}
}
}
}
int main(int argc, const char * argv[]) {
int arr[] = {1, 2, 3,10, 25, 26, 30, 31, 32, 33, 100, 101, 103, 104,105, 106,108};
PrintConsecutiveNumbers(arr, 17);
return 0;
}
void PrintConsecutiveNumbers (int * array, int size) {
int i = 0; int j;
bool cont;
int start = array[0];
while (i < size) {
printf("%i",start);
cont = true;
for (j = 1; cont; j++) {
int nxtSeq = array[i+j];
if ((start+j)!=nxtSeq) {
cont = false;
if(j!=1) {
printf("-%i\n",array[i+j-1]);
} else {
printf("\n");
}
start = nxtSeq;
i+=j;
}
}
}
}
void PrintConsecutiveNumbers (int * array, int size) {
int i = 0; int j;
bool cont;
int start = array[0];
while (i < size) {
printf("%i",start);
cont = true;
for (j = 1; cont; j++) {
int nxtSeq = array[i+j];
if ((start+j)!=nxtSeq) {
cont = false;
if(j!=1) {
printf("-%i\n",array[i+j-1]);
} else {
printf("\n");
}
start = nxtSeq;
i+=j;
}
}
}
}
b = []
s = ""
for i in range(1, len(a)):
if not(isContinuous) and a[i - 1] + 1 == a[i]:
isContinuous = True
s = s + str(a[i - 1]) + " - "
elif isContinuous and a[i - 1] + 1 == a[i]:
pass
elif isContinuous and a[i - 1] + 1 != a[i]:
isContinuous = False
s = s + str(a[i - 1])
b.append(s)
s = ""
else:
b.append(str(a[i - 1]))
In Objective-C:
+(void)printWithConsecutiveSegmentsInSortedArray:(NSArray*)sortedArray {
if (![sortedArray.lastObject isKindOfClass:[NSNumber class]]) {
return;
}
NSMutableArray *finalArray = [NSMutableArray new];
NSNumber *lastNumberInRun;
for (int i = 0; i < [sortedArray count]; i++) {
NSNumber *numberItem = sortedArray[i];
if (finalArray.lastObject == nil) {
[finalArray addObject:numberItem.stringValue];
continue;
}
if (lastNumberInRun == nil) {
if (((NSString*)finalArray.lastObject).integerValue + 1 == numberItem.integerValue) {
lastNumberInRun = numberItem;
if (i == [sortedArray count] - 1) {
if (lastNumberInRun != nil) {
[finalArray addObject:[NSString stringWithFormat:@"-%@", lastNumberInRun]];
}
}
continue;
}
[finalArray addObject:numberItem.stringValue];
} else {
if (lastNumberInRun.integerValue + 1 == numberItem.integerValue ) {
lastNumberInRun = numberItem;
if (i == [sortedArray count] - 1) {
if (lastNumberInRun != nil) {
[finalArray addObject:[NSString stringWithFormat:@"-%@", lastNumberInRun]];
}
}
continue;
}
[finalArray addObject:[NSString stringWithFormat:@"-%@", lastNumberInRun]];
lastNumberInRun = nil;
[finalArray addObject:numberItem.stringValue];
}
}
NSLog(@"%@", [finalArray componentsJoinedByString:@","]);
}
public static List<List<Integer>> findSegments(int[] a) {
if (a == null || a.length == 0) {
return null;
}
List<List<Integer>> r = new ArrayList<>();
List<Integer> l = new ArrayList<>();
l.add(a[0]);
if (a.length == 1) {
r.add(l);
return r;
}
for (int i = 1; i < a.length; i++) {
if (a[i] - a[i - 1] == 1) {
l.add(a[i]);
} else {
r.add(l);
l = new ArrayList<>();
l.add(a[i]);
}
}
if (l.size() > 0) {
r.add(l);
}
return r;
}
Swift example
var list = [1,2,3,10,25,26,30,31,32,33]
func printRanges(arr:[Int]) {
let results:[[Int]] = []
let divide = list.reduce(results) { t, i in
var mt = t
if var sl = t.last, l = sl.last {
if l - i == -1 {
sl.append(i)
mt.removeLast()
mt.append(sl)
} else {
mt.append([i])
}
return mt
} else {
mt.append([i])
return mt
}
}
let statement = divide.reduce("") { t, n in
var s = t
if n.count > 1 {
s = t + "\(n[0])-\(n[n.count - 1])"
} else {
s = t + "\(n[0])"
}
guard let l = divide.last where l == n else {
s = s + ", "
return s
}
return s
}
print(statement)
}
printRanges(list)
void findConsecutiveSegments (NSArray* numbers){
int start = [[numbers objectAtIndex:0] intValue];
int lastNumber = start;
int currentNumber;
for(int i = 1; i < numbers.count; i++){
currentNumber = [[numbers objectAtIndex:i] intValue];
if(currentNumber == lastNumber + 1){
lastNumber++;
}
else{
NSLog (@"%d - %d",start,lastNumber);
start = currentNumber;
lastNumber = currentNumber;
}
}
NSLog (@"%d - %d",start,lastNumber);
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
// insert code here...
NSArray *numbers = @[@1,@2,@3,@4,@5,@6,@10,@11,@12,@50,@51,@52,@55,@57,@100];
findConsecutiveSegments(numbers);
}
return 0;
}
-(void)sumRanges:(NSMutableArray *)array{
NSString *result;
int j = 0;
for(int i = 0; i < [array count]; i++){
result = [NSString stringWithFormat:@"%@\n%@", result, [array[i] stringValue]];
j = i + 1;
for(; j < [array count]; j++){
if([array[j] integerValue] != ([array[(j-1)] integerValue] + 1)){
if(j != i + 1){
result = [NSString stringWithFormat:@"%@ -> %ld", result, (long)[array[(j - 1)] integerValue]];
}
break;
}
}
if(j == [array count] && j != i + 1){
result = [NSString stringWithFormat:@"%@ -> %ld", result, (long)[array[(j - 1)] integerValue]];
}
i = j - 1;
}
NSLog(@"%@", result);
}
-(void)sumRanges:(NSMutableArray *)array{
NSString *result;
int j = 0;
for(int i = 0; i < [array count]; i++){
result = [NSString stringWithFormat:@"%@\n%@", result, [array[i] stringValue]];
j = i + 1;
for(; j < [array count]; j++){
if([array[j] integerValue] != ([array[(j-1)] integerValue] + 1)){
if(j != i + 1){
result = [NSString stringWithFormat:@"%@ -> %ld", result, (long)[array[(j - 1)] integerValue]];
}
break;
}
}
if(j == [array count] && j != i + 1){
result = [NSString stringWithFormat:@"%@ -> %ld", result, (long)[array[(j - 1)] integerValue]];
}
i = j - 1;
}
NSLog(@"%@", result);
}
class Main {
public static void solve(int[] array) {
if (array.length <= 0) return;
int prev = array[0];
int set = 0;
StringBuilder result = new StringBuilder();
for (int i=0; i<array.length; i++) {
if (i == 0) {
result.append(array[i]);
} else if (array[i] - prev > 1) {
if (set>1) result.append("-" + prev);
result.append("," + array[i]);
set = 0;
}
set++;
prev = array[i];
}
if (set>1) result.append("-" + prev);
System.out.println(result.toString());
}
public static void main(String[] args) {
int[] array = new int[]{1, 2, 3,10, 25, 26, 30, 31, 32, 33};
solve(array);
}
}
Swift version::::
func getConsecutiveSegment(_ array: [Int]) -> [String] {
var a = [String]()
var seq = ""
var i = 0
while i < array.count-1 {
if array[i] + 1 == array[i+1] {
var val = i+1
for j in i+1..<array.count-1 {
if array[j] + 1 != array[j+1] {break}
val += 1
}
seq = "(\(array[i])-\(array[val]))"
a.append(seq)
i = val+1
} else {
seq = "\(array[i])"
a.append(seq)
i += 1
}
}
return a
}
let sequence = getConsecutiveSegment([1,2,3,10,25,26,30,31,32,33])
func consecutiveSegments (InputArray: inout [Int]) {
//Check for evil Inputs
if InputArray.count < 1 {
return
}
if InputArray.count < 2 {
print("There is only 1 item in the array")
return
}
//We are Evil Input Free
var currIndex = 0
var nextIndex = 1
var outputArray = [String]()
var tempHoldArray = [Int]()
InputArray.append(0) //Add 0 to get last AnchorPoint
while currIndex < InputArray.count - 1 {
if differenceBtwCurrentandNextValue(input1: InputArray[currIndex], input2: InputArray[nextIndex]){
tempHoldArray.append(InputArray[currIndex])
currIndex += 1
nextIndex += 1
} else {
//If tempArryay isn't empty get the first anchorpoint element added
if !tempHoldArray.isEmpty {
outputArray.append("\(tempHoldArray[0]) - \(InputArray[currIndex])")
//Else No anchorPoint element was added
} else {
outputArray.append("\(InputArray[currIndex])")
}
tempHoldArray = [Int]() //DumpArray
currIndex += 1
nextIndex += 1
}
}
print("Output Array is \(outputArray)")
}
func differenceBtwCurrentandNextValue(input1 :Int, input2: Int) -> Bool {
return input2 - input1 == 1
}
//Use
var consecutiveSegment = [1, 2, 3, 10, 25, 26, 30, 31, 32, 33]
consecutiveSegments(InputArray: &consecutiveSegment)
A simple O(n) solution in swift
func getConsecutiveSegments(of array: [Int]) -> [[Int]] {
var result = [[Int]]()
var temp = [Int]()
for i in 0..<array.count-1 {
if array[i+1]-array[i] == 1 {
temp.append(array[i])
continue
}
temp.append(array[i])
result.append(temp)
temp = []
}
result.append(temp)
return result
}
getConsecutiveSegments(of: [1,2,3,10,15,16,31,32,33,34])
func getConsecutiveSegments(of array: [Int]) -> [[Int]] {
var result = [[Int]]()
var temp = [Int]()
for i in 0..<array.count-1 {
if array[i+1]-array[i] == 1 {
temp.append(array[i])
continue
}
temp.append(array[i])
result.append(temp)
temp = []
}
result.append(temp)
return result
}
getConsecutiveSegments(of: [1,2,3,10,15,16,31,32,33,34])
func getConsecutiveSegments(of array: [Int]) -> [[Int]] {
var result = [[Int]]()
var temp = [Int]()
for i in 0..<array.count-1 {
if array[i+1]-array[i] == 1 {
temp.append(array[i])
continue
}
temp.append(array[i])
result.append(temp)
temp = []
}
result.append(temp)
return result
}
getConsecutiveSegments(of: [1,2,3,10,15,16,31,32,33,34])
I came out with this answer in C++.
- byPaco September 15, 2015