## Expedia Interview Question

**Country:**United States

Sorry last comment submitted accidentally

If array is not sorted --

1. calculate avg O(n)

2. take 2 pointers one from starting and another from end of array

3. based on the condition whether element (from beginning and end) > avg move all end element to the beginning and replace end element -1

4. So overall time complexity O(n), space O(1)

This is 0(2n)...not sure if there's a better solution for unsorted array...

public static void checkAvg(int[] a1){

float sum=0;

float avg;

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

sum=sum+a1[i];

}

avg=(sum/(a1.length-1));

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

if(a1[i]>= avg){

System.out.println(a1[i]);

}

}

}

```
Integer[] findIntegers(int[] arr) {
int avg = 0;
for(int index = 0; index < arr.length; index++) {
avg+=arr[index];
}
avg /= arr.length;
ArrayList<Integer> integerArray = new ArrayList<Integer>();
for(int index=0; index < arr.length; index++ ) {
if(arr[index] > avg) {
integerArray.add(arr[index]);
}
}
return ArrayUtils.toPrimitive((Integer[])integerArray.toArray());
}
```

We can do in O(2n)

- temp February 04, 2012In the first pass you can calculate the sum of the array and get the avg

In the second pass can get the numbers greater than the avg

Is there a better solution for this problem