Number Patterns & Finding the Possible Smallest Numeric Value | Solution | C++

Given a Pattern containing only Ns and M’s. N represents ascending and M represents descending, Each character (M or N) needs to display sequence of numbers(2 numbers) explaining the ascending or descending order (for ex: 21 -> represents descending -> M). The second character in the pattern takes the last digit from first character and builds the sequence and so on.

Number Patterns & Finding the Possible Smallest Numeric Value | Find Lowest Numeric Value Matching the Pattern

There could be multiple numbers satisfying the pattern. The goal is to find out the lowest numeric value following the pattern.

Constraints:

Input can have maximum 8 characters.
Output can have Digits from 1-9 and Digits can’t repeat.
In case of no possible output or incorrect input value (like blank /null /NON M or N character) please return -1.

Example Section:

Input : M

Output: 21 (2 -> 1 shows descending and possible smallest numeric value. Even 65 or 74 can qualify, but 21 being the smallest numeric value is the correct answer)

Input : MNM

Output: 2143 (M represents descending 2->1 , N represents ascending 1->4 (1 is coming from last character) , M represents descending 4->3(4 is coming from last character sequence) -- There would be many numbers qualifying the pattern like 3142, 8796, 6241 etc.. 2143 is the lowest numeric value for this pattern sequence.)

Solution

int findPossibleSmallestNumberMatchingPattern(string pattern)
{
    int currMax = 0, last = 0;
    string res = "";
    for (int i = 0; i < pattern.length(); i++)
    {
        int decreasing = 0, j = i + 1;
        if (pattern[i] == 'N')
        {
            while (j < pattern.length() && pattern[j] == 'M')
            {
                decreasing++;
                j++;
            }
            if (i == 0)
            {
                currMax = decreasing + 2;
                ++last;
                res += ('0' + last);
                res += ('0' + currMax);
                last = currMax;
            }
            else
            {
                currMax = currMax + decreasing + 1;
                last = currMax;
                res += ('0' + last);
            }
            for (int k = 0; i < decreasing; k++)
            {
                --last;
                res += ('0' + last);
                i++;
            }
        }
        else if (pattern[i] == 'M')
        {
            if (i == 0)
            {
                while (j < pattern.length() && pattern[j] == 'M')
                {
                    decreasing++;
                    j++;
                }
                currMax = decreasing + 2;
                res += ('0' + currMax);
                res += ('0' + (currMax - 1));
                last = currMax - 1;
            }
            else
            {
                res += ('0' + (last - 1));
                last--;
            }
        }
    }
    if (res.length() == 0)
        return -1;
    return stoi(res);
}

TagsOA 2025codinggoldman sachsnumber patterns

Raunit Verma
Technical Writer at CodingKaro

Share this on