Minimum number of steps to flip cards deck

Question

This is a Contest problem not a home work.

Given N cards facing down, you have to flip all the N cards facing up. If you are flipping ith card then, i-1,i,i+1 will flipped. For eg: if N = 3, then minimum no of steps will be 1.
Given N cards, we have to calculate the minimum no of steps to flip all the cards up.

Initially i thought it is kind of fibonacci, Let N = 2,3,4 and minimum steps Min = 1,1,4 but if N = 6, then the minimum steps will be 2. I am struck here, Could anyone please help ?

Answer 1

The cases for N=1, 2, and 3 are easy.

For N = 3k, this is easy. Just flip over k cards starting with the second one.

For N = 3k+1, first flip both cards on the ends, which flips over 4 cards. Then we have 3k-3 cards left over, which is divisible by 3, which can be easily flipped in k-1 moves.

For N = 3k+2, first choose the first card, which flips 2 cards. Now you have 3k cards left to flip, which is easily done in k flips.