# October LunchTime UNofficial Editorials (First two problems) Revised

### Problem: Buggy Calculator

#### Problem Statement

Add two number A and B without carrying forward any value.

#### Solution

The above sum can also be written as

let A consist of M digits and B consist of N digits

let S[i] denote ith digit of required sum of A and B, A[i] be ith digit of A and B[i] be ith digit of B. (starting from unit, ten’s…).

For every digit i < Max(A,B)

S[i] = (A[i]+B[i])%10

Simply calculate this and output. Suppose you have a string (or char array) C storing digits if your answer, unit place at leftmost position.

Int f = 0;

String output = “”;

for(i = C.length-1; i >= 0;i–){

If(C[i] != ‘0’)f = 1; // for digit int array, replace ‘0’ with 0.

If f==1 out.append(C[i]);

}

if(f==0)print(0);

else print out;

If you feel you have a better idea for above, feel free to share in comments.

My Solution [Here]

### Problem: Maximum Number

#### Problem Statement

Given a number N, output Maximum number possible which satisfy constraint that number is multiple of 6. If no such number possible print -1.

#### Solution

First thing to know:

1. Every multiple of 2 has 0,2,4,6 and 8 at unit’s place. (I know You know this )
2. Sum of digits of Every multiple of 3 is also divisible by 3.

For checking divisibility by 6, it is sufficient to check divisibility by both 2 and 3.

Then, Following cases arise:

I. Digit at unit’s place is odd

In this case, if digit at ten’s place is also odd, then number cannot be made a multiple of 6. Thus print -1.

If ten’s place digit is even. delete unit’s place digit from given number. Now, if the resultant number is divisible by 3, print that number. Else print -1.

II. Digit at unit’s place is Even

In this case, multiple choices are there.

Let sum be sum of digits of given number. We can delete any digit d (except unit place digit if ten’s place digit is odd, so that the number remains a multiple of 2) for which sum%3 == d%3. This works because after deleting that digit, sum is a multiple of 3.

Now, to maximize this number, we need to find the digit at largest place satisfying above condition. This works because:

Take example number 4510222

sum of digits = 4+5+1+2+2+2 = 16

sum%3 = 1

Now, we can delete digits 1 and 4 (because 1%3=3, 4%3 = 1)

If we delete 1, we get number 450222

If we delete 4, we get number 510222

We delete the largest digit (leftmost) for which the next digit is greater than deleted digit. This is necessary to avoid following case

Number 7510222

Digits 7 and 1 can be deleted according to above solution, giving numbers 510222 and 750222 respectively. Here, deleting largest (leftmost) index give smaller result because 7 > 5. This worked in above case because 4<5.

Correct Solution

Find leftmost digit satisfying constraints

1. sum%3==digit%3
2. digit < Immediately next digit

In case no digit is found such that digit < Immediately Smaller digit, find Rightmost digit for which digit > Immediately right digit. This works because of following saying. There’s a well known saying (since now only :D) If you can’t maximize the addition of something, try to minimize it’s reduction. It’s the Same thing.

Just delete that digit and print the answer.

In case no digit satisfy sum%3==digit%3, print -1. (Example number 222)

Here’s my

``````


Enjoy Coding. :D

Feel free to ask anything... as always :)

: https://www.codechef.com/viewsolution/15981433
: https://www.codechef.com/viewsolution/15988110``````
12 Likes

For the second question my solution is O(n) but still giving TLE, please look into this:- https://www.codechef.com/viewsolution/15998898

Mate, Your solution is O(n^2) because Substring function itself take O(N) time because it has to transverse whole string. Further, using Integer.parseInt this many times, you can simply store a number in array, ith element of array being ith digit of number (from left to right or right to left, as you feel comfortable with. ).

2 Likes

hey taran my code is giving wa in 1st subtask. any testcase where it might fail? https://ideone.com/yKzrA3

Mate, i replied on your thread too. I’m still working with your solution only. sorry bro didn’t see then. thanks For the first question why is my solution giving WA in Subtask 2?

@vishaldugyala I guess u haven’t taken care of the fact that no.of digits may be different

Try Following test case.

1

55 54

No problem mate.

By the way, why are you using variable p in your code??

1 Like

Thanks Taran! Great job helping out others. Kudos!

Thanks mate. Is erase function also linear in Time???

@taran_1407 but wouldn’t the calculator print exactly 09 only?

Which language you are talking about mate??

I work with java. Either share code link. Nope, It isn’t mentioned in problem but a calculator always print 9, not 09. You may try. Yes, but since the calculator is faulty and skips carry i thought it should print 5555+5555 as 0000.
By the way, the calculator isn’t that faulty 