Day 17 | Grandma Laura and Apples | Lucky Tickets | C++

Today we will be solving 2 problems, both have a mathematical approach to the solution0

Grandma Laura and Apples | C++ Implementation

The key point to note here is that Grandma sold all her apples and we are given instructions about how she sold the apples. So if we start from the end, because we know the value at the end, and run in reverse of what she did, she can get the count of apples she brought to the market.

Let me explain, with sample test case 2

3 10
halfplus
halfplus
halfplus

After index 2 step, we will reach 0

But she gave away half, so must have reached 0.5

and since it was halved, hence it should be 1 before she sold it

After index 1 step, we will reach 1 (shown above)

But she gave away half, so must have reached 1.5

and since it was halved, hence it should be 3 before she sold it

After the index 0 steps, we will reach 3 (shown above)

But she gave away half, so must have reached 3.5

and since it was halved, hence it should be 7 before she sold it

So basically if apples we halved, then she must have cnt*2 apples earlier, hence grandma will be earning cnt*P

If apples were halfplus, then she must have (cnt*2 + 1) apples earlier, hence grandma will be earning cnt*P + P / 2 (half apple)

Lucky Tickets | C++ Implementation

This is a fun question.

Few common knowledge points

1. A number is divisible by 3 if the sum of digits is divisible by 3

2. If S is sum of digits of X, then S % 3 = X % 3

Using the two above points we can notice that, if we append two numbers A and B, then

append(A,B) % 3 = (A%3 + B%3) % 3

Reason:

append(A,B)%3 = sum of digits of A % 3 + sum of digits of B % 3

Using point 2

append(A,B)%3 = A % 3 + B % 3

Now we know that we have to make append(A, B) % 3 = 0 (modular mathematics)

hence if A % 3 = 0, then B % 3 = 0

A % 3 = 1, then B % 3 = 2

A % 3 = 2, then B % 3 = 1

Thus we can make pair of max(count of elements % 3 = 1, count of elements % 3= 2) + count of element % 3 = 0 / 2