**Given an int array which might contain duplicates, find if it is a sequence. ** **Eg. {45,50,47,46,49,48}** **is a sequence 45, 46,47,48,49,50** **Sorting is an obvious solution. Can this be done in O(n) time and O(1) space**

** (Or) Write a method that takes an int array of size m, and returns (True/False) if the array consists of the numbers n...n+m-1, all numbers in that range and only numbers in that range. The array is not guaranteed to be sorted. (For instance, {2,3,4} would return true. {1,3,1} would return false, {1,2,4} would return false. **

**By working with a[i] % a.length instead of a[i] you reduce the problem to needing to determine that you've got the numbers 0 to a.length - 1.**

**Approach:** **Example array: A = {4, 1, 3, 3, 2}** **1. get the min and max.** **min=1 and max=4** **2. if (max - min) > A.length then "its NOT a sequence".** **3. else for each element in A[i] do the following:** **a. calculate A[i] - min till A[i]-min=i;** **i=0; 4 - 1 = 3, swap A[0] and A[3]** **Now we have A = {3, 1, 3, 4, 2}** **Again, ** **i=0; 3 - 1 = 2, now A[0] and A[2] are same so swap A[0] and A[length-1] and put A[length] = infinite.** **A = {2, 1, 3, 4, INF}** **Again,** **i=0; 2 - 1 = 1, swap A[0] and A[1], ** **A = {1, 2, 3, 4, INF}** **i=1; 2 - 1 = 1 (which is same as i)** **similarlty for i=2, i=3** **finally we have A as,** **A = {1, 2, 3, 4, INF}**

public static boolean isSequence(int A[])

{

int min = Integer.MINIMUM;

int max = Integer.MAXIMUM;

int len = A.length;

for(int i=0;i<len;i++)

{

if(A[i] < min)

{

min = A[i];

}else if(A[i] > max)

{

max = A[i];

}

}

if(max-min > A.length)

return false;

int i=0;

while(i<len)

{

while(i<len && i != (A[i] - min))

{

if(A[A[i] - min] == A[i])

{

A[i] = A[len-1] ;

A[len-1] = Integer.MAXIMUM;

len = len-1;

}else

{

int k = A[i] - min;

int temp= A[i];

A[i] = A[k];

A[k] = temp;

}

}

i++;

}

for(int i=1;i<len;i++)

{

if((A[i] - A[i-1]) != -1

return false;

}

return true;

}

## No comments:

Post a Comment