HELP PLEASE-Chef and a Beautiful Digit

[1vf9z8AR]

append the digit d to the decimal representation of N (d becomes the least significant digit of N), then remove one occurrence of one digit from the decimal representation of N.

This line is important.

When I did this question. I tried these operations on different numbers and found a pattern:)

[ne555]

hint:
1999999999 is smaller than
2000000000

[Zivojin]

The number of digits in a number will never change,only the order of the digits.So you must somehow mangage to put the digits with lowest value on the beginning.In your number digits must be in the ascending order.digit on place n is lower or equal than a digit n+1;
Example:
112334455-you can not get lower number than this if Chef digit is higer or equal to the greatest digit in a number(Chef digit 7,no point going further you will only get bigger number)
11324455(Here 2 is on the fourth place and 3 is on the third place so even if a chef has a digit 9,by eliminating 3 you will get a lower number)
11244559-chef put 9 but 11244559 is lower than 11324455
If is possible you can put a number in array or a vector and there you can do manipulation with digits.

[jonnin]

I gave a hint in the other thread on this one too. I showed how to calculate the # of changes you need to make, and it can be directly converted to actually make the changes (left that to you guys to do, but I was able to convert it from counting to doing it in about 10 min).

you don't need to do all that much manipulation to build the output. Its O(N) to generate the answer. I ended up doing a C/C++ string mashup. I am low-intermediate with c++ strings and can't always get them to do what I want. I am now trying to get the C out of what I did for practice.

Edit... actually, I will share, it at least gives you guys the algorithm/idea even if the code is horribad. Note that while it has 2 loops, the total iterations is just the length of the input string.

EDIT: much better. main is still a bit clunky but the function is twice as fast after elimination of the extra string.

edit 3.. this has a flaw and gives wrong answer for some inputs. I know why. Taking a new look.

#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;


void foonum(char c, string s)
{	
    int i = s.length()-1;
    int j = 0;
    int count = 0;
   while(s[i] >= c && i) //find the breakpoint** (if any) where we want to keep digits (from least significant up in this loop)
   {     
	 i--;   //instead of appending char c n times to a string, just count them. 
	 count ++;
   }   
  for(j = 0; j <= i; j++) //work most significant down, printing keepers 
   {	                            //and skipping/counting discards. 
	  if(s[j] < c)
	  {
	   cout << s[j];
	  }	
       else count++;
   }  
  for(j = 0; j < count; j++) //print all the appended chars at once. 
	  cout << c;
  cout << '\n';
}

int main()
{  
  srand(19);
  int i,j;
  char ch[100] ={0};
  char c;
for(i = 0; i < 1000000; i++)
{
  for(j = 0; j < 15; j++)
	  ch[j] = rand()%9+'1';
  c = rand()%9+'1';
  cout << ch << " " << c << " ";  
  foonum(c,(string)ch);   
}	
 
}

** the reason for breaking it up into 2 sections is that the rules on when to replace changes. if you are replacing with '3' for example, and the input contains many 3s, there may be some you want to discard and some you want to keep. eg 3311 you want to discard the leading 3s and replace, to get 1133. but if you had 3333 already, you do nothing, keeping all 4. Splitting it the way I did accounts for this need ... walk through a couple to see it.

line 25, that &&i took a bit to debug, most of the time was spent tracking that down. The dangers of hands-on manipulations... can't miss the little details...

[STD8C542]

inputs:
3
6589 4
632154 4
892543 6

outputs:
4444
144444
236666

is this correct?

[jonnin]

yes.

I got mine fixed but I do not like it. I ended up finding the lowest value repeatedly (from where it left off last time, so still O(N)) and back filling. It feels brute forceish but the time was just as good as my broken stuff above (which was 1M/5 sec including generation of the test cases, so probably about 1M in ~2 sec).