PROBLEM LINK:
Setter:
Tester:
Editorialist: Abhishek Pandey
DIFFICULTY:
Cakewalk
PRE-REQUISITES:
Observation, Looping.
PROBLEM:
People are going to ATM in groups of 3. Given positions of Ramu and Lata, we have to tell if its possible for them to go in the same group or not, if they are at K th and $(K+1)$th position respectively.
STRATEGY:
This question can be easily solved by taking cases and exhausting all possibilities.
QUICK EXPLANATION:
We notice people at positions {3k+1,3k+2,3k+3} go in same group. Since Lata is just behind Ramu, she can always be in his group expect when Ramu is at $3k+3$th position, i.e. if his position K is divisible by 3.
TimeComplexity- O(1) for every T.
EXPLANTION:
The first person is at position 1, second is at position 2…and so on. We are given that Ramu is at K th position, and Lata is a $(K+1)$th position. The position of people in queue is like this-
1,2,3,4,5,6....,K,K+1,...N
Lets start forming groups to see how grouping is done. Following the statement in question, we see that positions in same group follow the pattern-
(1,2,3) , (4,5,6) , (7,8,9) .... where () denote that positions inside it are in same group. Its very easy to see that positions in same group are of form {(3k+1,3k+2,3k+3)}. Lets analyse case by case on when Ramu and Lata can be in same group.
If Ramu is at position 3k+1
If Ramu is at $3k+1$th position, then Lata is at $3k+2$th position. By above grouping pattern, we see that they lie in same group.
If Ramu is at position 3k+2
Again, same as above. Ramu is at position 3k+2 while Lata is at position 3k+3 and hence in same group.
If Ramu is at position 3k+3
We see that 3k+3 was the last position in group. This means that Lata cannot be in the same group now. She is now at the beginning position of next group.
Hence, from above we can conclude that if K%3==0 (i.e. Ramu’s position is a multiple of 3), then Lata and Ramu will be in different groups.
SOLUTION:
WHAT IF:
What if we twist the question so that, you are allowed to place Lata anywhere before Ramu if she isnt in same group as his? Will it change our answer in any way? Also, what if N is not divisible by 3? Will it affect the answer?
Ans: No. First two cases remain exactly same, since Lata and Ramu are in same group.
When not in same group, Ramu is at last position of group. Placing Lata in front of him will push him out of the group! Also, our answer seems to be independent of N, and only depending on K. So it should not get affected by changing N.