Find Next Higher Number With Same Digits

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int num = 37723971;
            string numStr = num.ToString();
            for (int i = numStr.Length - 2; i >= 0; i--)
            {
                //Scan for the first pivot digit i.e iterating from right to left check for the first digit smaller than its immediate right
                if (int.Parse(numStr[i].ToString()) < int.Parse(numStr[i + 1].ToString()))
                {
                    //Find the smallest digit higher than pivot digit on the right hand side of i
                    int smallestHigher = -1, position = -1;
                    for (int j = i + 1; j < numStr.Length; j++)
                    {
                        if (int.Parse(numStr[j].ToString()) > int.Parse(numStr[i].ToString()))
                        {
                            if (smallestHigher == -1)
                            {
                                smallestHigher = int.Parse(numStr[j].ToString()) - int.Parse(numStr[i].ToString());
                                position = j;
                            }
                            else
                            {
                                if ((int.Parse(numStr[j].ToString()) - int.Parse(numStr[i].ToString())) < smallestHigher)
                                {
                                    smallestHigher = int.Parse(numStr[j].ToString()) - int.Parse(numStr[i].ToString());
                                    position = j;
                                }
                            }
                        }
                    }
                    //Swap the smallestHigher digit with the pivot digit
                    if (position != -1)
                    {
                        char tempChar1 = numStr[i];
                        char tempChar2 = numStr[position];
                        numStr = numStr.Insert(i, tempChar2.ToString());
                        numStr = numStr.Remove(i + 1, 1);
                        numStr = numStr.Insert(position, tempChar1.ToString());
                        numStr = numStr.Remove(position + 1, 1);
                    }
                    //Sort (in increasing order) all the digits to the right of smallestHigher digit after swapping
                    char[] tempArray = numStr.ToCharArray(i + 1, numStr.Length - (i + 1));
                    Array.Sort(tempArray);
                    numStr = numStr.Remove(i + 1);
                    numStr = numStr + new string(tempArray);
                    break;
                }
            }
            Console.WriteLine(numStr);
        }
    }
}
37727139
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s