need help to direct my approach

[wowisay]

.

[jonnin]

hint: what is the smallest possible number? It has to do with chef's chosen digit against the most significant digits.
lets lock chef in at digit 4 for simplicity, and a few values...
999, that leading 900 is bigger than 400, so you need to replace it, so you need the maximum number of replacements, but you knew that with a single comparison of the most significant digit...

also, you DO know that you don't need to MAKE the change. You just need to say how many changes you need to make. You can directly compute that without doing the work.

[wowisay]

.

[jonnin]

how would I know, no code?
34457723453478
append 4, replace 5.
34477234534784
append 4, replace 7
34472345347844
append 4, replace 7
34423453478444
and now you see the problem.
you need to replace if equal too, if the numbers after are lower. the 4s have to go.
append 4, replace 4.
34234534784444
append 4, replace 4.
32345347844444
... and so on.

but this is actually DOING the work. You don't need this, you need to know how many to replace.
flat out, replace everything > 4 is your starting point.
577578 those MUST go, so you start your count with 6 changes that must happen.
then you check the equality ones, which are subjective to what is behind them whether they go or not.
34423453478444 //the 4s must go
34493453478444 //deleting the 4s increase the number due to the 9.
so start your count at 6, and find an efficient way to solve the equality question...
but can that ever really happen? You would have replaced the 9 with a 4. .. not sure, maybe you don't need this? Can you just count directly? Trying to think of a scenario where the 4s would stay in. The only one I can find is if the rest were all 4s.

[jonnin]

wait, isnt the answer 9 here?
34457723453478
replace all the > 4s:
34423434444444 6 moves

3 more moves ends it
34423434444444
32334444444444
the bold 4 never changes.

does this do what you want? I used c strings because there are 2 things string can't do. One is hackery of moving the zero terminal around (string ignores this), which I used here.

if this is correct, note that its O(N) absolute. that is, N is actually the length of the string; the sum of the number of iterations of the 2 loops = N.

#include <iostream>
#include <sstream>
#include <string>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cctype>
#include <algorithm>    // std::count_if
using std::cin;
using std::cout;
using std::endl;
using std::istringstream;
using std::string;
using std::vector;

using namespace std;

int main()
{
   int count = 0;
   char c = '4';
   char s[] = "34457723453478";
   unsigned int i = strlen(s) -1;
   while(s[i] >= c)
   {	
       count += s[i] > c;   
	   s[i--] = 0;  	   	   
   } 
   
   for(i = 0; i < strlen(s); i++)
   {
	  count += s[i] >= c;	  
   }
  cout << count;
}

anyone think of a scenario this does not cover? Its terrible, granted, but chef deserves no less than unmitgated hax for the way he acts :P

a similar idea would generate the actual values, of course, still in O(n). its just a little more string management. Counting the work is just the hint, you see.

[jonnin]

interestingly, because of doing it with strings, zero worked, it just gave leading zeros in some of the smallest number generated outputs. (I was extra lazy making test cases for it). Managed to produce the numeric smallest value, 1 mil in 10 sec including the test data generation. Redirected to file for that time, to avoid the I/O penalty.

and it probably could be faster, I didn't do a cleanup pass and wrote 1 char at a time for a portion of the output (which was the only way I could think of to shovel the above counter into the actual answer generator with minimal surgery).

[E0p9LyTq]

wowisay, STOP deleting the content of your posts. It is rude and unhelpful to others. This is NOT your private programming tutor service.