Thought Work coding challenge.

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.

for N = 3K answer is K.
But for N = 3K+1 , 3K+2 i am not able to find way how to flip.

As in one turn we have to flip three consecutive cards(i.e. i-1,i,i+1).So,if given number of cards are multiple of three then answer would be straight forward i.e. n/3. Now, the case when n is not the multiple of three , if you try to figure out on paper,you will came out with solution that is for all other numbers which are not the multiple of three answer would be n itself(Except corner cases 1 and 2 for which answer would be 1 obviously).

for ex. Let say n=7

Here , 0 = card facing down & 1 = card facing up

Initial state ==> 0 0 0 0 0 0 0

See here

So total number of flip operations = n = 7.
Similarly you can do for all other cases…!!! :slight_smile:

3 Likes

for n%3==0 ans is n/3 and for n%3!=0 is n except for n<3 answer is 1

The correct answer is ceil(n/3).

Proof-

Case 1- when n%3==0, select 2, 5, 8…i.e. elements which leave 2 as remainder when divided by 3.

Example- for n==6, initially 0 0 0 0 0 0

After 1st step, 1 1 1 0 0 0 (2 selected)

After 2nd step, 1 1 1 1 1 1 (5 selected)

Case 2- when n%3==1, select 1 and the last element, finally the elements 4, 7, 10 i.e. elements which divided by 3 leave remainder 1.

Example - for n=7, initially 0 0 0 0 0 0 0

After 1st step, 1 1 0 0 0 0 0 (1 selected, no i-1 present here)

After 2nd step, 1 1 0 0 0 1 1 (7 selected, no i+1 present here)

After 3rd step, 1 1 1 1 1 1 1 (4 selected)

So, basically after selecting the 1st and last element, we reduced the problem to smaller problem when n becomes divisible by 3.

Case 3- when n%3==2, select 1 and finally the elements 4, 7, 10 i.e. elements which divided by 3 leave remainder 1.

Example - for n=8, initially 0 0 0 0 0 0 0 0

After 1st step, 1 1 0 0 0 0 0 0 (1 selected, no i-1 present here)

After 2nd step, 1 1 1 1 1 0 0 0 (4 selected)

After 3rd step, 1 1 1 1 1 1 1 1 (7 selected)

So, basically after selecting the 1st we reduced the problem to smaller problem when n becomes divisible by 3.

Thus, final verdict- Hint for solving these type of questions, recursion/ dp, as these problems can be broken into smaller sub-problems which can be solved easily. Here the sub-problems were n=1, 2, 3, 4 and 5.

Also, if you want a bit tougher version of similar question, try https://www.codechef.com/problems/RNUM which was asked in Codechef Snackdown 2015: Round B.

Happy Coding…

@sangtaninaveen…I agree to your statement that for N<3 and N%3==0 ans is 1 and N/3 respectively but for N=5 isn’t the answer is 2. Consider the following:

Let 0 = card facing down & 1 = card facing up…(same notation as yours) and suppose N=5

initial state : 0 0 0 0 0

MOVE 1: flip 2nd card and the state becomes 1 1 1 0 0

MOVE 2: flip 5th card and the state becomes 1 1 1 1 1 (for i=5 , i+1th card doesn’t exist so only ith and i-1th card will be flipped)

Similarly it is for N=4…and so I would claim that for N>3 ans is 'ceil(N/3)…and for N<3 and N%3==0 ans is 1 and N/3 respectively

@sharad07 basically the point of confusion is that question is not properly mentioned , there(ThoughtWorks Coding Challenge) it was stated that all n cards are placed in round fashion and i have given explanation according to that.
Basically u r right when the case is that the cards are in linear fashion(ans = ceil(n/3), No doubt).

@sangtaninaveen applied the same logic where if (n/3==0) ans=n/3 else n. Just got 40 points.

    LL N;
	cin(N);
	LL ans;

	if (N % 3 == 0)
		ans = N / 3;
	else 
		ans = N;

	if (N lessthan 3)
		ans = 1;

	cout << ans << "\n";

@bajaj6 the same thing happened with me too and it took me a while to figure out the case for which it was going wrong i.e. 0.
your program prints 1 for 0 cards too :slight_smile:

1 Like

@docodon thanks.

1 Like

nice try… but your answers are wrong… see below for explanation.

@likecs actually mine answer is right as it is accepted on Thoughtworks Coding Challenge, basically the point of confusion is that question is not properly mentioned these n cards are placed in round fashion…
If they were linearly placed then that would be quite easy i.e. ceil(n/3).