How about a normal binary search ?
We know that X can be [0, 2^31 - 1].
Also if X is a valid configuration, all the values above X will too.
Monotonicity is all we need here.
So, take lo = 0 and hi = 2 ^ 31 - 1.
Now check, if your mid is a valid X.
If yes, X can lie between [0, mid]. If not, X will lie between [mid + 1,
2^31 - 1].
Here is an untested code.
typedef long long int64;
// If true, x is a valid configuration for v.
int
valid (int x, int N, vector <int64> &v) {
vector <int64> u = v;
u [0] -= x;
for (int i = 1; i < N; i++)
if (u [i] + x >= u [i - 1] + 1 && u [i] - x <= u [i - 1] + 1)
u [i] = u [i - 1] + 1;
else return false;
return true;
}
// A binary search over v for X [0, 2 ^ 31 - 1]
int
solve (int N, vector <int64> &v) {
int64 lo = 0, hi = 2147483647;
int ret = 0;
while (lo <= hi) {
int64 mid = lo + (hi - lo) / 2;
if (valid (mid, N, v)) {
ret = mid;
hi = mid - 1;
}
else lo = mid + 1;
}
return ret;
}
int
main () {
vector <int64> v;
v.push_back (5);
v.push_back (4);
v.push_back (3);
v.push_back (2);
v.push_back (8);
printf ("%d\n", solve (v.size (), v));
return 0;
}
On Wed, Jan 29, 2014 at 10:26 PM, bhargav <[email protected]> wrote:
> Given an array of integer elements
>
> *Your task is to*
>
> · write a function that finds the minimum value X that makes
> possible the following: generate a new array that is sorted in strictly
> ascending order by increasing or decreasing each of the elements of the
> initial array with integer values in the [0, X] range.
>
> o Example: Having the initial array [5, 4, 3, 2, 8] the minimum value
> for X is 3. Decrease the first element (5) by 3, decrease the second one
> (4) by 1, increase the third one (3) by 1, increase the forth one (2) by 3
> and do nothing to the last one (8). In the end we obtain the array [2, 3,
> 4, 5, 8] which is sorted in strictly ascending order.
>
> · print the result X to the standard output (stdout)
>
> Note that your function will receive the following arguments:
>
> · *v*
>
> o which is the array of integers
>
> *Data constraints*
>
> · numbers are in ascending order when arranged from the smallest
> to the largest number
>
> · strictly ascending order means that each element is greater
> than the preceding one (e.g. [1, 2, 2, 3] is NOT strictly ascending order)
>
> · the length of the array will not exceed 5000
>
> · the elements of any of the arrays are integer numbers in the
> [1, 231 -1] range
>
> *Efficiency constraints*
>
> · your function is expected to print the result in less than 2
> seconds
>
> *Example*
>
> *Input*
>
> *Output*
>
> v: 5, 4, 3, 2, 8
>
> 3
>
> any clues for the algo ??
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
