# Algorithm Help

William Koch

Ranch Hand

Posts: 76

posted 3 years ago

- 2

This is not a Java question but it is a computer science question in general (but if you help me with my solution we can write it in java or pseudo code if you want). If there is a more appropriate place to write this thread please let me know and I will move it.

If there is anyone who is really knowledgeable on algorithms that would be wonderful. If I am given an array and it is V-Shaped (meaning the values start off smaller, then hit a minimum value and then increase again) how can I find the minimum value. It is possible that there is only 1 value in the array. It is also possible the smallest value is the first value and they only get bigger. You can assume that the array is not empty and that no two consecutive values are equal but non consecutive values can be equal. Here is an example:

5,3,1,2,3,4,7

The minimum value here is 1.

If there is anyone who is really knowledgeable on algorithms that would be wonderful. If I am given an array and it is V-Shaped (meaning the values start off smaller, then hit a minimum value and then increase again) how can I find the minimum value. It is possible that there is only 1 value in the array. It is also possible the smallest value is the first value and they only get bigger. You can assume that the array is not empty and that no two consecutive values are equal but non consecutive values can be equal. Here is an example:

5,3,1,2,3,4,7

The minimum value here is 1.

posted 3 years ago

There are many ways to do this. The simplest is to iterate through the array, keeping track of the smallest found so far. When you get to the end of the array, you've found the smallest.

Why is this a challenge?

Why is this a challenge?

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

William Koch

Ranch Hand

Posts: 76

posted 3 years ago

- 1

Well haven't worked this completely out, but hope this helps. If you look at the center 3 values, the smallest one among the 3 is either in the center, left or right

If in center, you got your min

If left, you are in the right arm of your V, so recurse left

If right, you are in the left arm of your V, so recurse right

If in center, you got your min

If left, you are in the right arm of your V, so recurse left

If right, you are in the left arm of your V, so recurse right

posted 3 years ago
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

normally, a binary search would look at THE element at the center(-ish, if there are an even number of elements left). I don't think that is enough here.

I think you have to look at more than one element each time - the midpoint element and the elements on either side to see which side you need to divide in half next (or if you are done.

edit - I didn't fully read Jayesh's reply, but I think we are saying basically the same thing.

I think you have to look at more than one element each time - the midpoint element and the elements on either side to see which side you need to divide in half next (or if you are done.

edit - I didn't fully read Jayesh's reply, but I think we are saying basically the same thing.

William Koch

Ranch Hand

Posts: 76

William Koch

Ranch Hand

Posts: 76

posted 3 years ago

Pat, I totally wish I was right now. I hate school. Unfortunately I can't teach myself Object Oriented Programming (which is in Java) or Algorithms (oh which by the way is all in Ada). So those are my two weak classes. And even if I wanted to take them I would hire you guys here at the ranch to be my tutors ha ha

William Koch

Ranch Hand

Posts: 76

posted 3 years ago

Ok here is my thought: because it has to utilize binary search, you start at the middle. IF there is only one number, it is the smallest. IF their are multiple numbers in the array and number before and number after the middle number are larger than the middle number, than the middle number is the smallest.

Otherwise if the middle number is larger than the one before it, we know that the smallest number is to the left(or in the direction of the smaller values since it is a sorted array). So we make our upper bound 1 less than our current index. And our lower bound still remains the first index in the array. We would do the same if the middle number is larger than the one after it, meaning we need to change our lower bound to the 1 more than the center index and the upper bound to the last index. Make sense so far? Problem is I want to do this recursively but I am not sure how because the function (Ada equivalent of a Java method) only takes in an Integer Array. Here is what I have so far (Ada is pretty easy to read so you shouldnt have a problem if you know Java):

I need to put something after the elsif and the else statements in order to make a recursive call that keep the values of hi and lo and uses them when I pass in the same array. I thought about creating a new array but I do not know if that would hurt my goal of reaching O(log n) running time. Also I can only pass in an Array in this function. I can't add in paramters for the function except the array.

Otherwise if the middle number is larger than the one before it, we know that the smallest number is to the left(or in the direction of the smaller values since it is a sorted array). So we make our upper bound 1 less than our current index. And our lower bound still remains the first index in the array. We would do the same if the middle number is larger than the one after it, meaning we need to change our lower bound to the 1 more than the center index and the upper bound to the last index. Make sense so far? Problem is I want to do this recursively but I am not sure how because the function (Ada equivalent of a Java method) only takes in an Integer Array. Here is what I have so far (Ada is pretty easy to read so you shouldnt have a problem if you know Java):

I need to put something after the elsif and the else statements in order to make a recursive call that keep the values of hi and lo and uses them when I pass in the same array. I thought about creating a new array but I do not know if that would hurt my goal of reaching O(log n) running time. Also I can only pass in an Array in this function. I can't add in paramters for the function except the array.

William Koch

Ranch Hand

Posts: 76

posted 3 years ago

Jayesh,

There is a way. I figured it out. Here is what the problem statement is, and below it is my current solution that currently does not pass any test cases:

A V-shaped sequence consists of a (possibly empty) decreasing sequence followed by a (possibly empty) increasing sequence. For example,

5,3,1,2,3,4,7

is a V-shaped sequence, consisting of the decreasing sequence 5,3,1 followed by the increasing sequence 2,3,4,7. Alternatively, it can be viewed as the decreasing sequence 5,3 followed by the increasing sequence 1,2,3,4,7.

Given an array containing a V-shaped sequence, find and return the minimum value in the sequence. For example, given the above sequence, you would return 1.

For simplicity, you can assume that the array is non-empty and that no two consecutive values are equal. (Non-consecutive values may be equal, such as the 3s in the above sequence.)

Current Non Working Solution:

function V_Min(A : Int_Array) return Integer is

lo : Integer := A'First;

hi : Integer := A'Last;

mid: Integer := A(lo+hi)/2;

begin

if A'length = 1 then

return A(A'First); --A'First & A'Last return the first and last index so for example A(A'First) returns the value inside the first index and A(4) would return the value inside index number 4. In Ada Arrays can begin at 0 or 1 so to be safe I always use A'First to reference the first index.

elsif A'length = 2 then

return Integer'Max(A(A'First),A(A'Last));

end if;

if A(mid) < A(mid - 1) and A(mid) < A(mid + 1) then

return A(mid);

elsif A(mid) > A(mid - 1) then

hi := mid - 1;

return V_Min(A(lo..hi));

else

lo := mid + 1;

return V_Min(A(lo..hi));

end if;

end V_Min;

There is a way. I figured it out. Here is what the problem statement is, and below it is my current solution that currently does not pass any test cases:

A V-shaped sequence consists of a (possibly empty) decreasing sequence followed by a (possibly empty) increasing sequence. For example,

5,3,1,2,3,4,7

is a V-shaped sequence, consisting of the decreasing sequence 5,3,1 followed by the increasing sequence 2,3,4,7. Alternatively, it can be viewed as the decreasing sequence 5,3 followed by the increasing sequence 1,2,3,4,7.

Given an array containing a V-shaped sequence, find and return the minimum value in the sequence. For example, given the above sequence, you would return 1.

For simplicity, you can assume that the array is non-empty and that no two consecutive values are equal. (Non-consecutive values may be equal, such as the 3s in the above sequence.)

Current Non Working Solution:

function V_Min(A : Int_Array) return Integer is

lo : Integer := A'First;

hi : Integer := A'Last;

mid: Integer := A(lo+hi)/2;

begin

if A'length = 1 then

return A(A'First); --A'First & A'Last return the first and last index so for example A(A'First) returns the value inside the first index and A(4) would return the value inside index number 4. In Ada Arrays can begin at 0 or 1 so to be safe I always use A'First to reference the first index.

elsif A'length = 2 then

return Integer'Max(A(A'First),A(A'Last));

end if;

if A(mid) < A(mid - 1) and A(mid) < A(mid + 1) then

return A(mid);

elsif A(mid) > A(mid - 1) then

hi := mid - 1;

return V_Min(A(lo..hi));

else

lo := mid + 1;

return V_Min(A(lo..hi));

end if;

end V_Min;

posted 3 years ago

William, DoesNotWork doesn't help us. Can you explain what test cases you ran and what result you got? Did you try debugging? Is there is a difference in results of you have an array of even length vs odd length. Try with arrays of length 3 and 7 first( because they always yield odd numbered subsets) then try 4 and 8( always even subsets) try 5 and 9 ( this will first have odd numbered subset then even) then try 6 (first even then odd). In each of those cases try putting the smallest number in the center, off center and at the ends.

Also, If a. Length=2 then shouldn't you do integer.min

Also, If a. Length=2 then shouldn't you do integer.min

William Koch

Ranch Hand

Posts: 76

posted 3 years ago

Here is my final working solution and it passes 214/214 test cases! Thanks for all your help.

function V_Min(A : Int_Array) return Integer is

--These 3 values are the indices

lo : Integer := A'First;

hi : Integer := A'Last;

mid: Integer := (lo+hi)/2; --This was one big problem. I had to put lo + hi in parenthesis which I do not know how I missed something so obvious and yes it was Integer'Min instead of Integer'Max (another stupid mistake)

begin

if A'length = 1 then

return A(lo);

elsif A'length = 2 then

return Integer'Min(A(lo),A(hi));

else

--put("lo="); New_Line; put(lo);New_Line;

--put("hi="); New_Line; put(hi);New_Line;

--put("mid="); New_Line; put(mid);New_Line;

if A(mid) < A(mid-1) and A(mid) < A(mid+1) then

return A(mid);

elsif A(mid) > A(mid - 1) then

hi := mid - 1;

return V_Min(A(lo..hi));

else -- A(mid) > A(mid+1)

lo := mid + 1;

return V_Min(A(lo..hi));

end if;

end if;

end V_Min;

function V_Min(A : Int_Array) return Integer is

--These 3 values are the indices

lo : Integer := A'First;

hi : Integer := A'Last;

mid: Integer := (lo+hi)/2; --This was one big problem. I had to put lo + hi in parenthesis which I do not know how I missed something so obvious and yes it was Integer'Min instead of Integer'Max (another stupid mistake)

begin

if A'length = 1 then

return A(lo);

elsif A'length = 2 then

return Integer'Min(A(lo),A(hi));

else

--put("lo="); New_Line; put(lo);New_Line;

--put("hi="); New_Line; put(hi);New_Line;

--put("mid="); New_Line; put(mid);New_Line;

if A(mid) < A(mid-1) and A(mid) < A(mid+1) then

return A(mid);

elsif A(mid) > A(mid - 1) then

hi := mid - 1;

return V_Min(A(lo..hi));

else -- A(mid) > A(mid+1)

lo := mid + 1;

return V_Min(A(lo..hi));

end if;

end if;

end V_Min;

Consider Paul's rocket mass heater. |