[Community Puzzle] Next growing number

Puzzles
#22

Hello, the last test is not valid for me. I have used one loop to increment n and another one to compare each two digits, starting from left.
Any hint to optimize that ?

#23

Hi,
I can’t pass the Validator 1, can i have a similar execution of this validator pls ?

#24

General advice:
If your language can handle big integers, try to calculate N+1, convert it back to string and start from here, it will be wayyy easier.

2 Likes
#27

Think about what the problem is. If you have a 400 digit number, is incrementing by one something that can be done in a feasible amount of time? codingame has a limit of 2 seconds per test case roughly.

1 Like
#28

The last case really complicates things in javascript because the largest number possible 9007199254740991.

#29

Did you try this:

?

1 Like
#30

Didn’t know it existed. Thanks!

#31

How can it be solved without converting the String to number?

#32

By comparing digits, and maybe converting them to their ASCII values if needed.

#34

thanks. this pushed me over the hump.

turns out the worst thing that can happen to a codingamer is “accidentlally” pass the local tests. I guess as the old saying goes its better to know why a test fails than to not know why one passed :smiley:

#35

Thank you so much, your comment helped me solve it.

#36

I always fail Test 5 and Validator 5 because of timeout.
But my solution works for all numbers, and with enough time also for very big. How can it be optimised even more?
I use a function increment(char *num_as_string, int *len) which adds 1 to the string number.
My main function has the following structure:
+declaration&initialising of string, length and the bool growing.
+Hardcoded solution for numbers below 10, which have no previous digits that are bigger, and could be defined as ‘growing numbers’.
+A dowhile loop that first sets growing to true and uses the increment function once
+A for loop that goes trough the string, and checks if i+1th digit is smaller than i th digit, if yes then growing is false and it breaks out of the for loop
+if growing is still true at the and dowhile breaks, and the next growing number is printed.

Edit: Now I used another approach for the main() function. It works a lot better.
+declaration&initialising of string, length,the bool growing
+Hardcoded solution for numbers below 10.
+Using the Increment function in case n is already a growing num
+declaring a char ‘biggest’= first_digit of the num
+A for loop that goes trough the string

  • if i+1th digit is smaller than biggest, then n[i+1] (i_th digit) =biggest and growing=false
  • elif(n[i+1]>biggest){depends on growing …}
    +Output the modified string
#37

Please describe your approach instead of posting your code here.

Also, your code doesn’t timeout in Validator 1; the issue there is that your code produces a wrong answer.

#40

A faster way is to directly generate each digit of the answer, from left to right. Try finding a pattern or a rule of what the (n+1)th digit should be depending on the nth digit.

1 Like
#41

probably because you convert your string in int and not in long.

#42

for not convert in number and only manipulate char.
loop from last char to first char. if last char is 57 put 48 else add 1 to last char. if last char was 57 do the same on the previously and if the first char is 57 too add “1” to the initial string.