**Objective: **Given a array of unsorted numbers, check if all the numbers in the array are consecutive numbers.

**Examples:**

int[] arrA = {21,24,22,26,23,25}; - True (All the integers are consecutive from 21 to 26)int[] arrB = {11,10,12,14,13}; - True (All the integers are consecutive from 10 to 14)int[] arrC = {11,10,14,13}; - False (Integers are not consecutive, 12 is missing)

**Approach:**

**Naive Approach: **Sorting . Time Complexity – O(nlogn).

**Better Approach: Time Complexity – O(n).**

- Find the Maximum and minimum elements in array (Say the array is arrA)
- Check if array length = max-min+1
- Subtract the min from every element of the array.
- Check if array doesn’t have duplicates

for Step 4

**a) If array contains negative elements**

- Create an aux array and put 0 at every position
- Navigate the main array and update the aux array as aux[arrA[i]]=1
- During step 2 if u find any index position already filled with 1, we have duplicates, return false
- This operation performs in O(n) time and O(n) space

**b) If array does not contains negative elements – Time Complexity : O(n), Space Complexity : O(1)**

- Navigate the array.
- Update the array as for ith index :- arrA[arrA[i]] = arrA[arrA[i]]*-1 (if it already not negative).
- If is already negative, we have duplicates, return false.

**Complete Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class CheckArrayHasConsecutiveNos { | |

public Boolean WihtOutAuxArray(int [] arrA){ | |

//this method with work if numbers are non negative | |

int max = findMax(arrA); | |

int min = findMin(arrA); | |

if(arrA.length!=max–min+1) return false; | |

for(int i = 0;i<arrA.length;i++){ | |

arrA[i] = arrA[i]–min+1; | |

} | |

for(int i = 0;i<arrA.length;i++){ | |

int x = Math.abs(arrA[i]); | |

if(arrA[x–1]>0){ | |

arrA[x–1] = arrA[x–1]*-1; | |

} | |

else{ | |

return false; | |

} | |

} | |

return true; | |

} | |

public Boolean withAuxArray(int [] arrA){ | |

// this method with work even if numbers are negative | |

int [] aux = new int [arrA.length]; | |

int max = findMax(arrA); | |

int min = findMin(arrA); | |

if(arrA.length!=max–min+1) return false; | |

for(int i = 0;i<arrA.length;i++){ | |

arrA[i] = arrA[i]–min; | |

aux[i] = 0; | |

} | |

for(int i = 0;i<arrA.length;i++){ | |

if(aux[arrA[i]]==0){ | |

aux[arrA[i]]=1; | |

} | |

else{ | |

return false; | |

} | |

} | |

//If we have reached till here means , we satisfied all the requirements | |

return true; | |

} | |

public int findMax(int [] arrA){ | |

// find the maximum in array | |

int max = arrA[0]; | |

for(int i = 1;i<arrA.length;i++){ | |

if(max<arrA[i]){ | |

max = arrA[i]; | |

} | |

} | |

return max; | |

} | |

public int findMin(int [] arrA){ | |

// find the minimum in array | |

int min = arrA[0]; | |

for(int i = 1;i<arrA.length;i++){ | |

if(min>arrA[i]){ | |

min = arrA[i]; | |

} | |

} | |

return min; | |

} | |

public static void main (String[] args) throws java.lang.Exception | |

{ | |

int [] arrA = {21,24,22,26,23,25}; | |

CheckArrayHasConsecutiveNos i = new CheckArrayHasConsecutiveNos(); | |

System.out.println(i.withAuxArray(arrA)); | |

int [] arrB = {11,10,12,14,13}; | |

System.out.println(i.WihtOutAuxArray(arrB)); | |

int [] arrC = {11,10,14,13}; | |

System.out.println(i.WihtOutAuxArray(arrC)); | |

} | |

} |

**Output**:

true true false

We can also sort the array and thn check for consecutive numbers by adding one to previous element – complexity O(nlogn)

we can find the smallest number say smlNo; and we know the size of the array say S, using formula SumOfSNumbers with start element as smlNo, SumOfSNumbers = S/2(2*smlNO + (S-1)*1);

Now sum all the array numbers in tempSum .

Match tempSum with SumOfSNumbers , if both are equal return true otherwise false.

TimeComplexity – O(n)