Interview Question Categories

FIND NEXT HIGHER NUMBER WITH SAME DIGITS

FIND NEXT HIGHER NUMBER WITH SAME DIGITS


namespace FindNextHigherNumWitSameDigits
{
    class Program
    {
        public static int[] IntToIntArr(int Num)
        {
            int r = 0;
            List<int> li = new List<int>();
            while (Num > 0)
            {
                r = Num % 10;
                li.Add(r);
                Num = Num / 10;
            }
            li.Reverse();
            return li.ToArray();
        }

        public static int IntArrToInt(int[] NumArr)
        {
            int Num = 0;
            for (int i = 0; i< NumArr.Length; i++)
            {
                Num = Num * 10 + NumArr[i];
            }
            return Num;
        }

        public static int GetNextHigherNumWitSameDigits(int Num)
        {
            if (Num < 10) return Num;

            int[] NumArr = IntToIntArr(Num);
            int prev = NumArr[NumArr.Length - 1];

            int i = NumArr.Length - 2;

            //Find the first number which is smaller than the prev 
            //number travelling from rear end
            for (; i >= 0; i--)
            {
                if (prev > NumArr[i]) 
                {
                    break;
                }
                prev = NumArr[i];
            }

            if (i == -1) return Num;

            int smallIndex = i+1;

            //Find the smallest number greater than 'NumArr[i]' towards 
            //right of 'NumArr[i]'.
            for (int j = i+2; j < NumArr.Length; j++)
            {
                if (NumArr[j] > NumArr[i] && NumArr[j] < NumArr[smallIndex])
                    smallIndex = j;
            }
            
            int temp = NumArr[smallIndex];
            NumArr[smallIndex] = NumArr[i];
            NumArr[i] = temp;
            Array.Sort(NumArr, i + 1, NumArr.Length - i - 1);
            return IntArrToInt(NumArr);
            
        }

        static void Main(string[] args)
        {
            Console.WriteLine(GetNextHigherNumWitSameDigits(12354));
        }
    }
}

5 comments:

  1. How about take int array from the given number and sort in desc and write the number.

    ReplyDelete
    Replies
    1. That will give the max number not the next max.

      Delete
  2. Hi, read the title clearly, It says next higher number, not the highest number.

    ReplyDelete
    Replies
    1. Thanks!.I just figured it out.

      Delete
  3. I just want avoid the sorting can you please check it.

    public static int GetNextHigherNumWitSameDigits(int Num)
    {
    if (Num < 10) return Num;

    int[] NumArr = IntToIntArr(Num);
    int prev = NumArr[NumArr.Length - 1];

    int i = NumArr.Length - 2;

    //Find the first number which is smaller than the prev
    //number travelling from rear end
    for (; i >= 0; i--)
    {
    if (prev > NumArr[i])
    {
    break;
    }
    prev = NumArr[i];
    }

    if (i == -1) return Num;

    int smallNo = NumArr[i];

    //int smallIndex = i + 1;
    prev = NumArr[NumArr.Length - 1];
    NumArr[i] = prev;

    //Find the smallest number greater than 'NumArr[i]' towards
    //left of 'NumArr[i]'.
    for (int j = i + 1; j < NumArr.Length; j++)
    {
    //if (NumArr[j] > NumArr[i] && NumArr[j] < NumArr[smallIndex])
    // smallIndex = j;
    prev = NumArr[j];
    NumArr[j] = smallNo;
    smallNo = prev;

    }

    //int temp = NumArr[smallIndex];
    //NumArr[smallIndex] = NumArr[i];
    //NumArr[i] = temp;
    //Array.Sort(NumArr, i + 1, NumArr.Length - i - 1);
    return IntArrToInt(NumArr);

    }

    ReplyDelete