Interview Question Software Engineer / Developers
A[0] will be either -1 or 1
Check A[0] and put that value in rest of the array (the requirement is to make all elements of A equal).
O(N) solution:
1. In a single scan find the min and max elements of the array.
2. If their difference is more than 2 then its impossible .
3. If less than 2 then either all the elements are to be made equal to min/max/ min+1
4. In a single scan just increase/decrease each element accordingly
O(N) solution:
1. In a single scan find the min and max elements of the array.
2. If their difference is more than 2 then its impossible .
3. If less than 2 then either all the elements are to be made equal to min/max/ min+1
4. In a single scan just increase/decrease each element accordingly
Soln:
1. In a scan, find the max, min element and also see if all the elements are odd or even or there is a mixture
2. if the array contains a mixture of odd, even then return -1
3. Minimum number of operations is (Max - Min)/2.
here I am trying to bring each number close to the avg
while solving this prob, I noticed that a solution is possible if and only if:
1. either all elements are odd
2. or all elements are even
otherwise no solution..
can some one validate this understanding?
thanks harleen... you helped me solve the problem
// if all are even elements or if all are odd elements, proceed, else return impossible
// avg = max + min / 2
// if element is less than avg, increment
// else, decrement
// do until max = min
oddCount = 0; evenCount = 0 , i=0;
while(i<A.length)
{
if(A[i]%2==0)
evenCount++;
else
oddCount++;
}
if(oddCount>0 && evenCount>0)
{
return -1;
}
max = a[i];
min = a[i];
for(int i = 1; i<A.length; i++)
{
if(a[i] > max)
max = a[i];
if(a[i] < min)
min = a[i];
}
noOperations = 0;
while(max!=min)
{
noOperations++;
avg = (max + min) / 2;
for(i=0;i<A.length;i++)
{
if(a[i]<avg)
a[i]++;
else
a[i]--;
}
max--;
if(avg > min)
min++;
else
min--;
}
How about sorting the array and making every element equal to the mid point of the array? That way, it is a trade-off for elements on either side (greater and smaller) and no element has to be incremented a large number of times ?
- Anonymous December 08, 2010Also, with the average, we face the risk of the average not being an integer, and thus the deferment may not be an integer either. In which case, we would never be able to achieve that value using the ++/-- operations allowed.