×

# 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 :D )
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. :P

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 code

Enjoy Coding. :D

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

4.0k31103
accept rate: 22%

 2 I think you can add something on how to avoid those leading zeroes. I was simple printing the array and wasted A HUGE CHUNK of my time because it was printing leading 0. And BTW, I feel the problem statement SHOULD specify that leading zeroes arent allowed. I mean, yeah, to many people "5555+5555=0000" would make sense. answered 29 Oct '17, 00:39 15.5k●1●20●66 accept rate: 18% 3 Agreed That ought to be the case, but i thought of real life calculators, which never print 0000. Maybe the author's calculator wasn't that faulty to print 0000. :D (29 Oct '17, 00:43) 2 Possible XD. Imagine my reaction when I opened comment section after 20min only to realzie that leading zeroes are giving WA. I was like, "...................... (xinfinity)XDXD" (29 Oct '17, 00:47) Happens Mate... (29 Oct '17, 00:58)
 1 hey taran can u share your fb profile link or can you send me req.? Needed to talk to you personally. :) answered 29 Oct '17, 00:47 1.8k●6●14 accept rate: 22% How Come?? Surely you can ask anything here mate.. (29 Oct '17, 00:55) I see you haven't participated in lunchtime.. Ask away mate... (29 Oct '17, 01:00)
 0 For the second question my solution is O(n) but still giving TLE, please look into this:- https://www.codechef.com/viewsolution/15998898 answered 28 Oct '17, 23:57 63●7 accept rate: 0% 2 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. :) ). (29 Oct '17, 00:04) @taran_1407 the very first solution that passed is O(N^2)! Can you please look at his code and please comment that whether the test cases are weak or he has made some optimization ? (29 Oct '17, 08:34) pk3012★ link to the code : https://www.codechef.com/viewsolution/15981694 (29 Oct '17, 08:39) pk3012★ Probably weak test cases... (30 Oct '17, 12:55)
 0 hey taran my code is giving wa in 1st subtask. any testcase where it might fail? https://ideone.com/yKzrA3 answered 29 Oct '17, 00:15 23●3 accept rate: 0% Mate, i replied on your thread too. I'm still working with your solution only. :) (29 Oct '17, 00:18) sorry bro didn't see then. thanks :) (29 Oct '17, 00:22) No problem mate. (29 Oct '17, 00:26) 1 By the way, why are you using variable p in your code?? (29 Oct '17, 00:26) 1 just remove the line where you have checked the value of p and AC :) the idea is that when you get the value lesser, in the position nearer to the units place it will lead to better solution than that in the higher digits ! (29 Oct '17, 09:25) pk3012★
 0 For the first question why is my solution giving WA in Subtask 2? answered 29 Oct '17, 00:22 1 accept rate: 0% Try Following test case. 1 55 54 Correct answer 9 Your answer 09 (29 Oct '17, 00:26) @taran_1407 but wouldn't the calculator print exactly 09 only? (29 Oct '17, 00:28) Nope, It isn't mentioned in problem but a calculator always print 9, not 09. You may try. :) (29 Oct '17, 00:30) Yes, but since the calculator is faulty and skips carry i thought it should print 5555+5555 as 0000. Thanks for replying though. (29 Oct '17, 00:34) 1 No problem at all. By the way, the calculator isn't that faulty :D (29 Oct '17, 00:36)
 0 @vishaldugyala I guess u haven't taken care of the fact that no.of digits may be different answered 29 Oct '17, 00:25 23●3 accept rate: 0% Mate, in his solution, that matters not. Because he used the condition a>0 || b > 0 If one of them is zero, it will be automatically ignored. (29 Oct '17, 00:44)
 0 Thanks Taran! Great job helping out others. Kudos! answered 29 Oct '17, 00:27 865●2●14 accept rate: 10% Thanks mate. :) (29 Oct '17, 00:27)
 0 Is erase function also linear in Time??? answered 29 Oct '17, 00:28 3★doramon 86●5 accept rate: 5% Which language you are talking about mate?? I work with java. Either share code link. :) (29 Oct '17, 00:29) Here is my sol:https://www.codechef.com/viewsolution/15995643 (29 Oct '17, 00:38) doramon3★ The logic of your code isn't clear to me. Can you elaborate?? (29 Oct '17, 00:40) for each i erased character at that place... And checked the string so formed is divisble by 6 or not check condition in O(1) condition: 1.check even or not 2.if yes check (sum-a[i])%3 or not I think it's just because erase giving Tle (29 Oct '17, 00:46) doramon3★ @taran_1407 plzz join this group,it gonna helpful for us!! https://www.facebook.com/groups/1232901383475983/ (29 Oct '17, 00:50) doramon3★ As far as i know about c++, String s = p itself takes Linear time, making your solution time out. (29 Oct '17, 00:53) showing 5 of 6 show all
 0 Thanks for the explanation :) Can you help me debugging my code please? LINK answered 29 Oct '17, 00:43 614●1●9 accept rate: 12% Your code can only delete 3,6 and 9 from given number due to line if(p%3==0) Further, no need to check sum%3==0 Simply check (sum-d)%3==0 where d is the deleted digit. (29 Oct '17, 00:49)
 0 t = int(input()) while t>0 : n = input() i = len(n) flag = 0 li = [] while i>0: copy = int(n[:i-1] + n[i:]) if copy%6 == 0: li.append(copy) flag = 1 i -= 1 if flag == 1: print(str(max(li)).rjust(len(n)-1, "0")) else: print("-1") t = t-1 I don't know why it was giving TLE although you have also used nested loops and hence O(n^2)... please help me? answered 29 Oct '17, 01:07 95●3 accept rate: 8% I did use two loops but not two nested loops. There's a difference. Nested loop is loop within a loop, which i haven't used and you have. That's what that make the difference. :) (29 Oct '17, 01:13) thanks mate, but loop will traverse at max six time because it is traversing digits. So how can it be TLE... I just can't understand. (29 Oct '17, 23:15) How come loop will transverse 6 times only?? Loop will transverse like 10^6 times as i know, (29 Oct '17, 23:57)
 0 https://www.codechef.com/viewsolution/16001364 Can you help me debugging my code please? link This answer is marked "community wiki". answered 29 Oct '17, 03:31 71●4 accept rate: 0% Mate, you are complicating your life a lot by using that vector V. Simply check for digit remainder 3 during a loop, check if sum%3 == d%3. It will give same reaults. Refer to my implementation and feep free to ask anythibg.. :) (29 Oct '17, 17:17)
 0 I'm getting WA in the second subtask in BUGCAL... Why? https://www.codechef.com/viewsolution/15984308 answered 29 Oct '17, 09:50 3★data2000 1●2 accept rate: 0% Your Code gives wrong input for 1 99999999 99999999 output: 88888880 But Unable to figure out the exact reason for WA @taran_1407 @vijju check out this code why showing wrong (29 Oct '17, 13:45) doramon3★ 1 Thats because of pow10 function, which stores result in double. Due to precision loss of ~${10}^{-8}$, it shows deviation at large values. (29 Oct '17, 14:05)
 0 My solution is in O(number of digits). I don't know why it is giving TLE. This is my solution. It is in Python. My logic is I calculate the number if I remove one digit, and check if it is divisible by 6 and greater than previously held value and replace it. Then append zeroes according to input if the first digit is removed. e.g:- 3268398 is input, num will hold the values (268398, 368398, 328398, 326398, 326898, 326838, 326839) in each iteration respectively. Will check if it is divisible by 6 and greater than previously divisible value. Thanks in advance. answered 29 Oct '17, 10:08 4★gomu 208●4 accept rate: 5% A must know thing for python coders. When dealing with large number, Even basic arithmetic operations like remainder cost time proportional to number of digits, making your solution O(N^2). Feel free to ask anything.... (29 Oct '17, 17:29)
 0 My code gives wrong ans.Any test case where it may fail? link:https://www.codechef.com/viewsolution/16002121 answered 29 Oct '17, 10:45 1★ayushi09 32●5 accept rate: 0% Well, i certainly can't find any test cases. First thing, keep your code clean, it will help degugging. Second thing, you haven't added last digit to sum after testing for impossible cases. (29 Oct '17, 17:43)
 0 for the second question ,every test case i checked is satisfied still i am getting a wrong answer please help me out pointing out just 1 test case that this code cannot run ?? https://www.codechef.com/viewsolution/15992968 answered 29 Oct '17, 10:54 3★spidy_j 41●3 accept rate: 0% you are getting -1 for 66666666666 (29 Oct '17, 13:40) spp____2★
 0 @taran_1407 can you give some testcases for 2nd question. answered 29 Oct '17, 11:16 1 accept rate: 0% Maybe you can ask problem setters for this.. They can provide much better test cases then i can. :) (29 Oct '17, 17:44) can u tell me the solution for 102 and 100 (29 Oct '17, 21:58)
 0 https://www.codechef.com/viewsolution/15988759 What is wrong in this code for BUGCAL? PLease help. Everything handled! answered 29 Oct '17, 11:39 17●3 accept rate: 0% Hey @shivam2296 ur code showing wrong for a.length
 0 @shivam2296 When you are swapping a&b then you should also swap the length also. answered 29 Oct '17, 12:07 1 accept rate: 0%
 0 Taran, Can you help me debug my code? It seems like I'm missing some corner cases. Edit: I'm sorry. The link was wrong. This is link to solution. https://www.codechef.com/viewsolution/16002813 answered 29 Oct '17, 12:34 0●1 accept rate: 0% it's showing Acess Denied :( (29 Oct '17, 13:46) doramon3★ That link was wrong! I changed it:D (30 Oct '17, 19:46) Hey Try the following test case 1 630 Correct answer is 60. Enjoy coding :D (PS:i won't tell the bug) (30 Oct '17, 23:44)
 0 Hey taran I am getting wa for the 2nd subtask in the problem BUGCAL. Any testcase where I might fail. Here's the link to my solution - link text answered 29 Oct '17, 13:30 1●1 accept rate: 0% Ur code printing leading Zeroes!! (29 Oct '17, 17:11) doramon3★ But i tested my code on clion and codechef compiler, it didn't printed any leading zeroes.Could you please specify the test case in which it printed leading zeroes. (30 Oct '17, 20:41)
 0 Hey @taran_1407, did you solve the third problem i.e. Optimal Subset? I have a conventional O(n^2) DP approach and optimizing it seems way too difficult to me and I can't even think of any other way to approach that problem too. Any suggestions on that? answered 29 Oct '17, 22:00 111●1●6 accept rate: 11% I got only 40 points in Optimal Subset using an observation. Just waiting for official editorial to find out whether its correct or not. :D (29 Oct '17, 22:44)
 0 Loving your explanations dude. well done C.A :P as your institute suggests answered 30 Oct '17, 02:27 469●10 accept rate: 0% Thanks.. PS: I am a first year student, not yet CA. Long way to go!! (30 Oct '17, 19:15)
 0 @taran_1407 I am getting run-time error. I tried too much to find where i am getting this but failed. please help me. this is my code--> https://www.codechef.com/viewsolution/15994545 thank you answered 30 Oct '17, 09:57 18●2 accept rate: 12% Mate Try following tesr case 1 10000200000000000 (30 Oct '17, 13:00)
 0 Can anyone give me a test case where my code fails? It's working well for all the test cases I checked. PLEASE HELP ME!!! I'm storing the digits in an array from one's place. Then I am iterating through all the digits and finding the new number by removing that particular digit. Now, I'm checking whether it is divisible by 6 or not and if it is then I check whether it is largest number possible which I initially set to -1. At last I'm printing the new number with k-1 digits where k is the total number of digits in the initial number. Leading zeros will be printed since I used %0*d and passed k-1 and maxnum to it. LINK:-My Solution answered 30 Oct '17, 14:31 2★ramini 61●5 accept rate: 8% Mate, You cannot take a number with 10^5 digits in int data type. You have to input it as a string. Try following test case. 1 10000200000000000 Second thing, Your solution try to delete one digit, check the resultant number. This way, Your solution has time complexity O(N^2), which won't even pass the time limit for number of digits upto 10^3. (30 Oct '17, 19:19)
 0 Taran, sorry for posting that link which didn't work. I updated it. Can you help me? answered 30 Oct '17, 19:48 0●1 accept rate: 0%
 0 In problem maximum number in my code I am not able to figure out mistake. It gives wrong answer on submission. Can anyone help me debugging it. Link to my code is Here. Please help :) answered 30 Oct '17, 21:41 3★jb1998 55●7 accept rate: 16% The link that I gave before was not working , Sorry for that.. Now I updated the link (30 Oct '17, 22:30) jb19983★ Try the test case 1 3602 Correct answer is 360 PS:what if last two digits are both even and last digit on deletion gives the maximum answer. Enjoy coding :D (30 Oct '17, 23:32)
 0 i dont know why my code is getting wrong anser. please help me; link is https://www.codechef.com/viewsolution/16015871 answered 31 Oct '17, 00:05 16●1 accept rate: 16% Try test case 1 660 Correct answer 66, your answer 60 (31 Oct '17, 00:14) thanks,buddy (31 Oct '17, 00:19)
 0 i dont know why my code is getting wrong answer, please help; link https://www.codechef.com/viewsolution/15998613 answered 02 Nov '17, 18:56 1 accept rate: 0% You cannot take a number with 10^5 digits as int data type. You have to take it as string. Try following test case 1 11100000000000000000000 Enjoy (02 Nov '17, 20:30) thanks much! (02 Nov '17, 21:49)
 0 simply just check when sum of the digit >= 10 take mod of the ans and store it in an array during calculation in O(n) time then print the same answered 02 Nov '17, 20:47 21●4 accept rate: 0%
 0 Hey can anyone plz tell me what's wrong with this code? https://www.codechef.com/viewsolution/15993064 answered 03 Nov '17, 16:58 11●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×64

question asked: 28 Oct '17, 23:54

question was seen: 2,192 times

last updated: 03 Nov '17, 16:59