CareerCup

(1) find max, min in array.
(2) if (max - min + 1 != n) return false;
(3) else do the following:
(a) subtract whole of the array with min value.
(b) for (i = 0; i < n; i++)
{
if(a[a[i]] < 0)
{
print false;
break;
}
else
a[a[i]] *= -1;
}
if ( i == n )
print true;
(c) restore the array i.e make all the elements positive by applying abs operator and then add min to each and every element.

can we do better than linear?

I gave 2 solutions

1. sort the array
2. use another array of booleans and then check uniqueness of each number but space complexity O(N)
3. i thought of it but could nt complete. Using the arithemetic progression formulas

Why not just traverse the array and find the product of all the elements. Then if the number of elements is n, the product should be equal to n!

find the min element and sum of all the elements in the array. Then use AM formula where a=min element and n=arraysize and d=1.

Uniqueness is the key here. If you get a solution for checking uniqueness of N elements between max and min then u have done ur job.

For the uniqueness only i had suggested having another array but again space complexity would be O(N)

how about using both multiply and addition - like even with non-consecutive input that yields correct sum the product won't be what it should be

1. if n<1 return false
2. go throu array with size of n to find min and sum.
3. return true if sum = n*min+n(n-1)/2; otherwise return false.

1. as above mentioned, find min, max. Check max-min = n-1, if it is false, return false, otherwise check step2
2. Map all numbers in the array to 1 to n natural numbers by scanning second time. You have min, then
a[i] = a[i]-min+1;
a[i] = a[i] * a[i];
sum = sum + a[i];

Then user the formula, sum of squares of n natural numbers, result = n(n+1)(2n+1)/2.
If sum and result are same, then you can say the numbers are consecutive.

this solution take space complexity of O(n), time complexity of O(2n) ~ O(n)

Sorry if this question is already solved. But here is my answer:
In first pass find min and max.
Check 1: max - min - 1 != n return false;
Check 2: Do a second pass and perform xor operation in following manner:
int temp = 0;
for (int i=0; i<n; i++){
temp = temp ^ i ^ (A[i] - min)
}
Finally, if temp==0 implies all number are different.

Note: All I wanted is to use solution of "How to find a duplicate element in an array of shuffled consecutive integers?"

why dont we simply check consecutive and find that they differ by 1 ???????
why are you making so hard

first find the minimum in 0(n) time
next find xor of all elements subtracting min from each element while taking xor.
ans=a[0]
ans=ans ^ (a[i]-min) for i=1 to n.
if ans ==0 return false
else true
time compl : 0(n) and space : 0(1)

step1:
find the min, max,length in o(n).
2. iterate thru the given array once again, subtract min from each number and mark the second array(boolean array) with true for that index
for(int i=0; i< arr.length; i++){
    booleanArray[arr[i] - min] = true;
}
3.iterate thru boolean array and see if there is any non true value - if there, then the given array is not consecutive.

For consecutive integers sum of numbers must be as below.

n + (n+1) + (n+2) + ... + (n+k-1) = kn + k(k-1)/2


For any other number function must return false. Simple!

i think we can solve the problem in O(n) time but we need another array of size (max-min+1). my method is find max and min from the given array "a". create an int array "check" of size (max-min+1). again scan the given array "a" and increment the value of check[a[i]-min]. if any element of check != 1 then return false. here is my code. ALL CONSTRUCTIVE COMMENTS ARE ALWAYS WELCOME.

public static void main(String [] args){
        int [] a = {2, 2, 3, 3, 4, 7, 7};
	boolean flag = false;
	int min = Integer.MAX_VALUE;
	int max = Integer.MIN_VALUE;
	for(int i=0; i<a.length; i++){
		if(a[i] < min){
			min = a[i];
		}
		if(a[i] > max){
			max = a[i];
		}
	}
	int [] check = new int[max-min+1]; 
	for(int i=0; i<a.length; i++){
		check[a[i]-min]++;
	}
	for(int i=0; i<check.length; i++){
		if(check[i] == 1){
			flag = true;
		}
		else{
			flag = false;
			break;
		}
	}
	if(flag){
		System.out.println("the array is consicutive");
	}
	else{
		System.out.println("the array is not consicutive");
	}
}

Step-1: Iterate whole array 'Arr' and Find 'MAX', 'MIN' and 'LENGTH'.
Step-2: if( MAX - MIN + 1 != LENGTH) return false;
Step-3: Generate a HashMap. Check if we have a collision with newly inserted value if so return false or else return that value from Arr to HashMap.
Step-4: If Step-3 iterates through all values of array 'Arr' without any collision then return true.

Complexity: Time O(n), Space O(n)

find minimum of array find the sum of elements of array , it should be (n-1)(n-2)/2 - n*min if yes return true else false.

min = Integer.MIN_VALUE;
for (i=0; i<a.length; i++) {
  if (a[i] < min)
    min = a[i];
}
Boolean flag = new Boolean();
Integer temp = new Integer();
for (i=0; i<a.length; i++) {
  if((a[i]-min) < a.length) {
    if (a[i] != a[a[i]-min] ) {
      flag = TRUE;
    } else flag = FALSE;
  } else {
    System.out.println('False');
    return;
  while ((a[i] != min+i) || flag) {
    temp = a[i];
    a[i] = a[a[i]-min];
    a[a[i]-min] = temp;
  }

Too lazy to finish the code, I guess you got what I am saying.

Keep an array of length n. In this array we will keep track the position of min and max. Initially both will point to starting of array.

Funda is to form a kind of circular array and keep on inserting elements in sorted manner. If element already exists at that position return false.
Insert first element at starting.
Second element if greater than max will be inserted to position (element-max) and max will be updated, else if less than min inserted at at (minPosition - min + element). If position is less than zero, insert from bottom of array to give impression of circular array.

Now for each element insert it into array.

for (i = 1; i < n ; i++ ) {
if (element <= min) {
    if (max - element > n)
	return false;
    //Insert at proper position, if element exists at this position return false;
} else if (element >= max) {
	if (element - min >n)
		return false;
	//Insert at proper position, if element exists at this position return false;
} else {// element lies between max and min, insert at proper position
	//Insert at proper position, if element exists at this position return false;
}

Didn't read all solutions here, sorry if it's a repitition.

1) find min O(n)
2)Subtract min from each element O(n)
3)Sum=n(n-1)/2... Sigma(0 to n-1) O(1) :\
4)Traverse array and keep subtracting each element from Sum O(n)
5)if Sum==0 return true else return false
6)Restore array by adding min if needed

1. Find max, say n, Expected sum s1 = n * (n+1) / 2
2. Find min, say m, Expected sum s2 = m *(m+1) /2

3. Sum of elements in the array s3
4. return s3 == s1 - s2;

this'll work right.