We can go by binary search approach like first consider the largest number as
it is an obvious sol^n then consider max/2 n so on running time O(log(max)) .
Sent from my BlackBerry 10 smartphone.
Original Message
From: atul anand
Sent: Wednesday 26 March 2014 12:20 PM
To: algogeeks@googlegroups.com
Reply To: algogeeks@googlegroups.com
Subject: Re: [algogeeks] Re: strictly sorting by adding or subtracting a range
of numbers
@bhargav : could you please explain your algorithmn
On 3/25/14, bhargav krishna yb <ybbkris...@gmail.com> wrote:
> Even i completed it :). It was from one of the coding challenges...
>
> public class Hill {
>
> /**
> * @param args
> */
> public static void main(String[] args) {
> // TODO Auto-generated method stub
> Integer[] l = new Integer[] {15,5, 4, 3, 2, 8};
> hill(l);
> }
> public static void hill(Integer[] l) {
> int max = 0;
> for(int i=0;i<l.length;i++) {
> if(max<l[i]) {
> max = l[i];
> }
> }
> int min =0 ;
> while(true) {
> int av = (max+min)/2;
> if(min==max) {
> if(isHill(l, av)) {
> System.out.println(min);
> }
> else {
> System.out.println("broke");
> }
> break;
> }
> if(isHill(l, av)) {
> max = av;
> }
> else {
> min= av+1;
> }
> }
> }
> public static Boolean isHill(Integer[] l, int i) {
> int prev = -1;
> for(int j=0;j<l.length;j++) {
> int max = Math.max(prev+1, l[j]-i);
> if(Math.abs(max-l[j])>i) {
> return false;
> }
> prev = max;
> }
> return true;
> }
> }
>
> On Tue, Mar 25, 2014 at 10:14 AM, Dan <dant...@aol.com> wrote:
>>
>>
>> I just stumbled upon this one (I know, a little late). At least this
>> way...
>> it's too late to be helpful if it was a Homework assignent. :-)
>>
>> This is one of those problems that, at first, appears difficult, but ,
>> upon
>> closer inspection, turns out to have a very straight forward (elegant?)
>> solution.
>>
>> Take any two adjacent values from the list... call them a & b
>>
>> In the worst case scenario, the value of a is higher than the value
>> of
>> b... a > b
>>
>> Therefore, we need an X value that solves the inequality.... a - X
>> <
>> b + X
>>
>> Rearrange this equation just slightly to another equivalent equation...
>> a
>> - b < 2X
>>
>> This indicates that a slightly different (but, still equivalent) problem
>> can
>> be solved to arrive at a correct solution.
>>
>> Only allow values from 0 to 2X, [0,2X] to be added to the original
>> values
>> in the array (ie. no subtractions). This simplifies things greatly and
>> allows for a clear algorithm solution that can be easily performed in a
>> single pass through the array. Essentially, you find a value of 2X that
>> works... then divide that in half, and convert the resulting float type
>> value to a whole integer value to get the final X value that solves the
>> 'original' problem statement.
>>
>> The fortran code below has been tested and appears to work just fine.
>> The real algorithm of note is the function routine: FUNCTION
>> TransformArray( v ).
>> Note that the important code is only 7 simple lines long and should
>> be easy to recode in most any language.
>> It runs extremely fast, even for array sizes of 10000.
>> There's also 'fluff' code here, written to test multiple test sets to
>> check
>> the value of X arrived and to time everything. at is the desired answer.
>>
>> Does anyone know of any Practical applications for this algorithm?? I'm
>> guessing it's just an interesting problem.
>>
>> Dan :-)
>>
>> Module Transform
>>
>> Contains
>>
>> Function TransformArray( v ) Result(x)
>> !---------------------------------------------------
>> ! Find a minium X value to transform the array, v(:)
>> ! Transformed array values can be negative. It is a trivial task to
>> ! alter this to guarantee no negative values in the transformed array.
>> !---------------------------------------------------
>> Integer, intent(in) :: v(:)
>> Integer :: x
>> Integer :: i, b
>> x = 0
>> b = v(1)
>> Do i = 2, Size(v)
>> b = Max( b+1, v(i) )
>> x = Max( x , b-v(i) )
>> End Do
>> x = Ceiling( x/2.0 ) ! smallest integer greater/equal to the
>> value.
>> End Function TransformArray
>>
>>
>> Subroutine Validate_X( v, x )
>> !---------------------------------------------------------------------
>> ! Given a value of x, see if the array can be successfully transformed
>> ! This is merely code to see if the X value arrived at is correct.
>> !---------------------------------------------------------------------
>> Integer, intent(in) :: v(:)
>> Integer, intent(in) :: x
>> Integer, allocatable :: vt(:), xt(:)
>> Integer :: i, n
>>
>> n = Size(v)
>> Allocate( vt(n), xt(n) )
>>
>> vt(1) = v(1) - x
>> xt(1) = -x
>>
>> Do i = 2, n
>> vt(i) = Max( vt(i-1)+1, v(i)-x )
>> xt(i) = vt(i)-v(i)
>> End Do
>>
>> write(*,'(a,29999i6)') ' v = ', v
>> write(*,'(a,29999i6)') ' xt = ', xt
>> write(*,'(a,29999i6)') ' vt = ', vt
>>
>> If( Any( abs(xt) > x ) ) Then
>> write(*,'(a)' ) ' A higher x value was required during the
>> transformation.'
>> write(*,'(a,i0,a)') ' X = ', x, ' does not work.'
>> End If
>>
>> If( Any( vt(1:n-1) >= vt(2:n) ) ) &
>> write(*,'(a)') ' ERROR: Transformed array is not in "Strictly
>> Ascending"
>> order!'
>>
>> End Subroutine Validate_X
>>
>> End Module Transform
>>
>>
>>
>> Program Main
>> !----------------------------------
>> Use Transform
>> Implicit None
>> Integer, parameter :: nmax=10000
>> Integer :: n, x
>> Integer, allocatable :: v(:)
>> Real, allocatable :: r(:)
>> Integer :: it1, it2
>>
>> Allocate( v(nmax), r(nmax) )
>>
>> call timer(it1)
>> write(*,*)
>> write(*,*) 'Test Case #1: array size = 5, Easy to check'
>> n = 5
>> v(1:n) = (/5,4,3,2,8/)
>> Call Solve_for_X()
>> write(*,*) '------------------------------------------'
>>
>> write(*,*)
>> write(*,*) 'Test Case #2 array size = 8, Easy to check'
>> n = 8
>> v(1:n) = (/8,12,7,15,10,20,12,16/)
>> Call Solve_for_X()
>> write(*,*) '------------------------------------'
>>
>> write(*,*)
>> write(*,*) 'Test Case #3: array size = 10000 w/ random array values up
>> to
>> 999'
>> n = 10000
>> Call Random_Seed()
>> Call Random_Number( r(1:n) )
>> v(1:n) = 1 + Int(999*r(1:n))
>> Call Solve_for_X()
>> write(*,*) '------------------------------------'
>>
>> call timer(it2)
>> write(*,*) 'Total time = ', Real(it2-it1)/100.0
>>
>> Contains
>>
>> Subroutine Solve_for_X()
>> !------------------------
>> x = TransformArray( v(1:n) )
>> write(*,'(a,i0)') ' X minimum = ', x
>>
>> Call Validate_X( v(1:n), x )
>>
>> ! Check to see if a smaller X value would have worked
>> write(*,*)
>> write(*,'(a,i0,a)') ' Check to see if x = ', x-1, ' will work:'
>> Call Validate_X( v(1:n), x-1 )
>> End Subroutine Solve_for_X
>>
>> End Program Main
>>
>>
>> Test Case #1: array size = 5, Easy to check
>> X minimum = 3
>> v = 5 4 3 2 8
>> xt = -3 -1 1 3 -2
>> vt = 2 3 4 5 6
>>
>> Check to see if x = 2 will work:
>> v = 5 4 3 2 8
>> xt = -2 0 2 4 -1
>> vt = 3 4 5 6 7
>> A higher x value was required during the transformation.
>> X = 2 does not work.
>> ------------------------------------------
>>
>> Test Case #2 array size = 8, Easy to check
>> X minimum = 5
>> v = 8 12 7 15 10 20 12 16
>> xt = -5 -5 1 -5 1 -5 4 1
>> vt = 3 7 8 10 11 15 16 17
>>
>> Check to see if x = 4 will work:
>> v = 8 12 7 15 10 20 12 16
>> xt = -4 -4 2 -4 2 -4 5 2
>> vt = 4 8 9 11 12 16 17 18
>> A higher x value was required during the transformation.
>> X = 4 does not work.
>> ------------------------------------
>>
>> Test Case #3: array size = 10000 w/ random array values up to 999
>> X minimum = 5466
>> v = 422 430 670 62 37 561 287 : : : 565 664
>> 389
>> 273
>> xt = -5466 -5466 -5466 -4857 -4831 -5354 -5079 : : : 4923 4825
>> 5101
>> 5218
>> vt = -5044 -5036 -4796 -4795 -4794 -4793 -4792 : : : 5488 5489
>> 5490
>> 5491
>>
>> Check to see if x = 5465 will work:
>> v = 422 430 670 62 37 561 287 : : : 565 664
>> 389
>> 273
>> xt = -5465 -5465 -5465 -4856 -4830 -5353 -5078 : : : 4924 4826
>> 5102
>> 5219
>> vt = -5043 -5035 -4795 -4794 -4793 -4792 -4791 : : : 5489 5490
>> 5491
>> 5492
>> A higher x value was required during the transformation.
>> X = 5465 does not work.
>> ------------------------------------
>> Total time = 9.99999978E-03
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> --
>> You received this message because you are subscribed to a topic in the
>> Google Groups "Algorithm Geeks" group.
>> To unsubscribe from this topic, visit
>> https://groups.google.com/d/topic/algogeeks/ClXwlon0eXo/unsubscribe.
>> To unsubscribe from this group and all its topics, send an email to
>> algogeeks+unsubscr...@googlegroups.com.
>
>
>
> --
> -bhargav krishna
>
> --
> 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 a topic in the Google
Groups "Algorithm Geeks" group.
To unsubscribe from this topic, visit
https://groups.google.com/d/topic/algogeeks/ClXwlon0eXo/unsubscribe.
To unsubscribe from this group and all its topics, 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.
