#Raihan zamil code
To handle this, following is the final code with a one line condition added to check for consecutive same numbers: def almostIncreasingSequence(sequence): While the test is sorted, its on an increasingSequence as demanded in the problem. Īs noted in his comments, we need to differentiate between a 'sorted' and an 'increasingSequence' in this problem. This solution still fails on lists such as.
#Raihan zamil full
It was here when I could see that if this condition is true for the full list, then we have what is required - an almostIncreasingSequence! So I completed my code this way: def almostIncreasingSequence(sequence): Thus bringing me to this: for i in range(len(sequence)): I started visualizing the list by removing an element at a time during iteration, and check if the rest of the list is a sorted version of itself. i.e.: if sequence=sorted(sequence):ĭetermine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array (at a time). It fails the time constraint on the last hidden test set alone in the exercise.Īs the problem name suggests, I directly wanted to compare the list to its sorted version, and handle the 'almost' case later - thus having the almostIncreasingSequence. My attempt at this is really short and works for all scenario. What's important in this is to look at the list after removing one element at a time from it, and confirm that it is still a sorted list. The reason why your modest algorithm fails here (apart from the missing '=' in return) is, it's just counting the elements which are greater than the next one and returning a result if that count is more than 1. If no such pair exists, return -1."""Īnd here are the tests I used. """Return the first index of a pair of elements in sequenceįor indices k-1, k+1, k+2, k+3.
If you do want to avoid those temporary lists, here is other code that has a more complicated pair-checking routine. Return False # Deleting either does not make increasing Return True # Deleting later element makes increasing Return True # Deleting earlier element makes increasing If first_bad_pair(sequence + sequence) = -1: Sequence by removing no more than one element from the array.""" """Return whether it is possible to obtain a strictly increasing """Return the first index of a pair of elements where the earlierĮlement is not less than the later elements. Here is Python code that passes all the tests you show. If you do not like the up-to-two temporary lists that are made by combining two slices of the original list, the equivalent could be done with comparisons in the original list using more if statements. I can think of other algorithms but this one seems the most straightforward. If either of those work, fine, otherwise not fine.
If it works, fine, but if not try deleting the earlier or later offending elements. Then one algorithm that would work is to check the original list. Otherwise, return the index of the earlier element: this will be a value from 0 to n-2. Make a routine first_bad_pair(sequence) that checks the list that all pairs of elements are in order. You have a right idea, checking consecutive pairs of elements that the earlier element is less than the later element, but more is required. My code: def almostIncreasingSequence(sequence):īut it can't pass all tests. Alternately, you can remove 2 to get the strictly increasing sequence. You can remove 3 from the array to get the strictly increasing sequence.
There is no one element in this array that can be removed in order to get a strictly increasing sequence.įor sequence, the output should be: almostIncreasingSequence(sequence) = true. Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.įor sequence, the output should be: almostIncreasingSequence(sequence) = false
0 kommentar(er)
