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 <ybbkris...@gmail.com> 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 algogeeks+unsubscr...@googlegroups.com.
>
--
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 algogeeks+unsubscr...@googlegroups.com.
