Strictly Increasing Sequence of Integers

Hey, guys. This is a problem on CodeFights that I'm trying to solve. Given a sequence of integers as an array, I have to determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.
I am passing 15/17 test cases, and here are the two test cases I am failing.

Input: sequence: [40, 50, 60, 10, 20, 30]
Output: true
Expected Output: false

Input: sequence: [1, 2, 5, 3, 5]
Output: false
Expected Output: true

I know where the flaws in my code occurs for these test cases, but I'm not sure how to fix this. I want to make my code as simple as possible.

 ``1234567891011121314151617181920212223`` `````` bool almostIncreasingSequence(std::vector sequence) { int count = 0; for (int i = 0; i < sequence.size() - 1; i++) { if (sequence[i + 1] <= sequence[i]) { count++; if (sequence[i + 2] == sequence[i]) { count++; } } if(count > 1) { return false; } } return true; } ``````
(sequence[i + 2] == sequence[i])
I really don't understand this equality check.

AND it would appear that on occasion i+2 > size of vector (??)

---------
 ``123456`` ``````seems to me like all you need is for(i = 0; i s[i] c++; if c > 1, fail else succeed.``````

Last edited on
 ``12345678910111213141516`` ``````bool almost_strictly_increasing( const std::vector& seq ) { if( seq.size() < 2 ) return true ; int cnt_non_increasing = 0 ; int prev = seq.front() ; for( std::size_t i = 1 ; i < seq.size() && cnt_non_increasing < 2 ; ++i ) { if( prev < seq[i] ) prev = seq[i] ; else ++cnt_non_increasing ; } return cnt_non_increasing < 2 ; }``````
@JLBorges
You didn’t check that against OP’s second sequence. (Both prev and i need more careful adjustment in the `else` clause. I also recommend making prev an index into seq instead of a value.)
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748`` ``````#include #include bool almost_strictly_increasing( const std::vector& seq ) { if( seq.size() < 2 ) return true ; int cnt_non_increasing = 0 ; int prev = seq.front() ; for( std::size_t i = 1 ; i < seq.size() && cnt_non_increasing < 2 ; ++i ) { if( prev < seq[i] ) prev = seq[i] ; else ++cnt_non_increasing ; } return cnt_non_increasing < 2 ; } bool almost_strictly_non_decreasing( const std::vector& seq ) { if( seq.size() < 2 ) return true ; int cnt_decreasing = 0 ; int prev = seq.front() ; for( std::size_t i = 1 ; i < seq.size() && cnt_decreasing < 2 ; ++i ) { if( prev <= seq[i] ) prev = seq[i] ; else ++cnt_decreasing ; } return cnt_decreasing < 2 ; } int main() { std::cout << std::boolalpha // first sequence << almost_strictly_increasing( { 40, 50, 60, 10, 20, 30 } ) << '\n' // false << almost_strictly_non_decreasing( { 40, 50, 60, 10, 20, 30 } ) << '\n' // false // secons sequence << almost_strictly_increasing( { 1, 2, 5, 3, 5 } ) << '\n' // false << almost_strictly_non_decreasing( { 1, 2, 5, 3, 5 } ) << '\n' ; // true }``````

http://coliru.stacked-crooked.com/a/f2dfb7b695524c89
1, 2, 5, 3, 5 is almost strictly increasing.

If you remove the middle 5 then the sequence is 1, 2, 3, 5.
That test should return true.
That is right.
I see now what Duthomhas meant by "need more careful adjustment in the else clause."
Somebody else had a go at this problem recently:
http://www.cplusplus.com/forum/beginner/226505/#msg1032980
It's obviously the "in" challenge!
(@rabster's code at the end of that thread also fails this particular test.)

 ``12345678910111213141516171819202122232425262728293031323334353637383940`` ``````#include #include #include using namespace std; template bool almostIncreasing( const vector &a ) { bool available = true; int last = a.size() - 1; for ( int i = 1; i <= last; i++ ) { if ( a[i] <= a[i-1] ) // Must remove either a[i] or a[i-1] { if ( !available ) return false; // No lives left; bye-bye if ( i == last ) return true; // Got this far: just remove the last one if ( i > 1 ) // If a[0]>=a[1] remove a[0]; so only check when i > 1 { bool ok = ( a[i-2] < a[i-1] && a[i-1] < a[i+1] ) || ( a[i-2] < a[i] && a[i] < a[i+1] ); if ( !ok ) return false; // Neither removal will work } available = false; // Last life just went } } return true; } //====================================================================== int main() { vector a; int i; string line; cout << "Input an array as a single line: "; getline( cin, line ); stringstream ss( line ); while( ss >> i ) a.push_back( i ); cout << "Almost strictly increasing? " << boolalpha << almostIncreasing( a ); }``````

 ```Input an array as a single line: 40 50 60 10 20 30 Almost strictly increasing? false```

 ```Input an array as a single line: 1 2 5 3 5 Almost strictly increasing? true```
Last edited on
tricksey ... I see now that mine fails the first seq.
Fixed generic version
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455`` ``````#include #include template bool solveableSequence(const T& container) { if (container.size() == 0) { return false; } if (container.size() == 1) { return true; //depends on whether or not a sequence with 1 element qualfies } std::size_t operations = 0; const auto begin = std::begin(container); auto last = begin; for (auto iter = last, end = std::prev(std::end(container)); iter != end;) { auto next = std::next(iter); if (!(*last < *next)) { //< is for strict ascending, <= is for loose ascending ++operations; if (last != begin) { auto prev = std::prev(last); if (*prev < *next) { last = next; } if (operations > 1) { return false; } } } else { last = next; } iter = next; } return operations == 1; // <= for already sorted data; } template void solveSequence(const T& container) { std::cout << std::boolalpha << solveableSequence(container) << std::endl; } using initList = std::initializer_list; int main() { solveSequence(initList{1, 2, 1, 2}); solveSequence(initList{8, 8, 8, 7, 7, 7}); solveSequence(initList{1, 2, 2, 3}); solveSequence(initList{1, 2, 3, 2, 3}); solveSequence(initList{1, 2, 3, 2, 4}); solveSequence(initList{1, 2, 3, 6, 5}); solveSequence(initList{9, 8, 7}); solveSequence(initList{1, 2, 3, 6, 5, 4}); solveSequence(initList{1, 2, 5, 3, 5}); solveSequence(initList{40, 50, 60, 10, 20, 30}); }``````
Last edited on
This challenge is a little trickier than it appears at first glance.

Here’s my entry.

 ``12345678910111213141516171819202122`` ``````template bool almost_strictly_increasing( Iterator first, Iterator last ) { if (std::distance( first, last ) < 3) return true; auto u = std::adjacent_find( first, last, std::greater_equal () ); if (u == last) return true; auto v = std::adjacent_find( u + 1, last, std::greater_equal () ); if (v != last) return false; auto a = ( u == first) or (u[-1] < u[1]); auto b = (++u == --last) or (u[-1] < u[1]); return a or b; } template bool almost_strictly_increasing( const std::vector & seq ) { return almost_strictly_increasing( seq.begin(), seq.end() ); }``````

Just so you all know, I did some pretty extensive testing with this (which y’all should have done!) and lastchance is the only other poster who got it right.

And by extensive, I mean permuting every possible combination of a sequence and testing against a no-fail (but O(n³)) algorithm.

────────────────────────────────────────────────────────────

@leorio
Your idea of testing against items separated by a middle item is a good one. It fails, however, in specific edge cases.

What you need to do is verify that there are a maximum of two strictly increasing sequences. At the join between the sequences, you have two possible cases:

• the first element of the disordered pair needs to be ignored

1 2 5 3 4
↑

• the second element of the disordered pair needs to be ignored

6 7 5
↑

Both of these are edge cases. The first may occur as the first item in a sequence, and the second may occur as the last.

So you must test for those for conditions.

────────────────────────────────────────────────────────────

@rabster
 ``` Perform automated tests over a permuted sequence ([Y]/n)? Values to permute? 1 2 3 4 1 2 3 4 ----FAIL (true, false) 1 2 4 3 pass (true) 1 3 2 4 pass (true) 1 3 4 2 pass (true) 1 4 2 3 pass (true) 1 4 3 2 pass (false) 2 1 3 4 pass (true) 2 1 4 3 pass (false) 2 3 1 4 pass (true) 2 3 4 1 pass (true) 2 4 1 3 pass (false) 2 4 3 1 pass (false) 3 1 2 4 ----FAIL (true, false) 3 1 4 2 pass (false) 3 2 1 4 pass (false) 3 2 4 1 pass (false) 3 4 1 2 pass (false) 3 4 2 1 pass (false) 4 1 2 3 ----FAIL (true, false) 4 1 3 2 pass (false) 4 2 1 3 pass (false) 4 2 3 1 pass (false) 4 3 1 2 pass (false) 4 3 2 1 pass (false) FAILED 3 of 24 tests. Perform automated tests over a permuted sequence ([Y]/n)? Values to permute? 1 5 5 7 1 5 5 7 pass (true) 1 5 7 5 pass (true) 1 7 5 5 pass (false) 5 1 5 7 ----FAIL (true, false) 5 1 7 5 pass (false) 5 5 1 7 pass (false) 5 5 7 1 pass (false) 5 7 1 5 pass (false) 5 7 5 1 pass (false) 7 1 5 5 pass (false) 7 5 1 5 pass (false) 7 5 5 1 pass (false) FAILED 1 of 12 tests. ```

You also erroneously return `false` for an empty sequence. By definition, an empty sequence is sorted.

Hope this helps.
Yeah, I should have tested against more values but at the time of writing I was at school and a bit rushed. I'll make sure to test in these kinds of situations.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657`` ``````#include #include template bool solveableSequence(const T& container) { if (container.size() <= 1) { return true; } const auto begin = std::begin(container); auto last = begin; std::size_t operations = 0; for (auto iter = last, end = std::prev(std::end(container)); iter != end;) { auto next = std::next(iter); if (!(*last < *next)) { //< is for strict ascending, <= is for loose ascending if (operations) { return false; } ++operations; if (last != begin) { auto prev = std::prev(last); if (*prev < *next) { last = next; } } else if (*next < *last) { last = next; } } else { last = next; } iter = next; } return operations <= 1; // <= for already sorted data; } template void solveSequence(const T& container) { std::cout << std::boolalpha << solveableSequence(container) << std::endl; } using initList = std::initializer_list; int main() { solveSequence(initList{1, 2, 1, 2}); solveSequence(initList{8, 8, 8, 7, 7, 7}); solveSequence(initList{1, 2, 2, 3}); solveSequence(initList{1, 2, 3, 2, 3}); solveSequence(initList{1, 2, 3, 2, 4}); solveSequence(initList{1, 2, 3, 6, 5}); solveSequence(initList{9, 8, 7}); solveSequence(initList{1, 2, 3, 6, 5, 4}); solveSequence(initList{1, 2, 5, 3, 5}); solveSequence(initList{40, 50, 60, 10, 20, 30}); solveSequence(initList{5, 1, 5, 7}); }``````