The problem definition is that

Given an additional digit 0 ≤ x ≤ 9, write a function that returns the integer that results from inserting x in n, such that its digits also appear in ascending order from left to right. For instance, if n = 24667 and x = 5, the function should return 245667.

My code

// the divisions are integer division, no floating point
int x(int n, int insertValue)
{
    if (n == 0) return 0;
    int val = x(n/10, insertValue);
    if((n) > insertValue)
    {
        int q = insertValue * 10   (n);
        return val * 100   q;
    }
    return val*10   (n);
}

For the case of, for example, x(2245,3), it outputs 223435. But I have already done with it while processing 224. It shouldn't go on adding the value to be inserted any more, I mean the 3 shouldn't be there before 5 .

I can come up with a solution that I can put in each recursion step a boolean flag that identify by taking modulo by 10 and dividing by 10 up to reach the single digit case. If there is no any identification, go in to that if block, else not. But it sounds too silly.

CodePudding user response：

When you're dividing recursively, you are actually going right to left, not left to right, so you should check if a digit is smaller than the one inserted and not greater (unless you always let the recursion reach n==0 condition and make your comparisons on your way out of it but that would be ineffective).

The second thing is that you do not break recursion once you inserted the digit (which you were aware of as I can see now in the question title), so it gets inserted repeatedly before every digit that is larger than insertValue. As to how to do it: you were already stopping recursion with if(n==0) condition, i.e. if n==0 the function stops calling itself (it returns immediately). When inserting the digit the difference is that you need to use the original value (n) to return from the function instead of passing it further.

At this point it works well for your example but there's also one border case you need to consider if you want the function to work property. When you have nothing to divide anymore [if(n==0)] you need to insert your digit anyway (return insertValue) so it does not get lost on the left edge like in x(2245,1) call.

Improvements for brevity:

• % has the same precedence as * and /, so brackets around it are not needed here.
• I removed val variable as it was now used only once and its calculation was not always necessary.

Here's the working code:

int x(int n, int insertValue){
    if(n == 0) return insertValue;
    
    //if insertion point was found, use original value (n)
    if(n <= insertValue)
        return n*10   insertValue;

    //if not there yet, keep calling x()
    return x(n/10, insertValue)*10   n;
}