WA in Maximum Number (MAXNUM3) LTIME53

Can someone give a test case where my code fails or rather guide me to the correct approach ?

After taking care of the last digit cases, I’m using a greedy approach to find the first number that on removal will lead to (sum of digits) %3=0 and has the next number greater than itself. If such a number doesn’t exist, I remove the lowest rightmost number that will lead to that result.

havent taken care of the case when last%2 == 0 and l2%2 == 0.

why u define soo much macro’s?

I applied the same technique, passed only subtask2.

Didn’t understand where the approach is wrong.

``````
[1]

[1]: https://www.codechef.com/viewsolution/15992745``````

In your code on line 73:

x < a[i+1]-‘0’ this condition is wrong because it doesn’t guarantee that the resulting number after deleting a digit will be greater than the one you found earlier.

Consider this test case:

Input

2

668

663

-1

66

Correct Output

66

66

Can anyone tell me due to which testcase it was showing wrong answer?

https://www.codechef.com/viewsolution/15992665

If you want another approach, Have a look here.

If you wannna find bug in your approach, explain it in a bit detail.

Can anyone give me a test case where my code fails? It’s working well for all the test cases I checked.

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.

Try the following:

333966 => 33966

369369 => 69369

123456 => 12456

123126 => 12312

654321 => 65421

162132 => 16212

167137 => 17137

137167 => 17167

That’s when the greedy approach is used.

consider the case 3 960. the answer should be 96

Input:

1

6666666666

Correct Output:

666666666

1 Like

I’m noob in java so I can’t help you with why your code gives no output but I can say that you’ve read the question wrong.
I see you’ve taken input as integer which is wrong because the input constraint says that input number can be of 10^5 digits long i.e input number can be 10^(10^5) which your long int input can’t handle.
Try implementing using string.

Hope it helps.

thanks @a_d_i

It would time out.

The solution time complexity is O(N^2) which won’t pass.

Further, the number can have 10^5 digits, thus, can’t be stored in int or even long long.