//
// Code to find the next higher number of a given number with same digits
//
#include <stdio.h>

// Comment the below line to remove debug prints
//
#define DEBUG_PRINT
 
typedef int digit;

int GetNextHighestWithSameDigits(int inputValue);

int main(int argc, char* args[])
{
  int val;

  val = 12345;
  printf("\nNextHighest(%d) = %d\n", val, GetNextHighestWithSameDigits(val));

  val = 13483;
  printf("\nNextHighest(%d) = %d\n", val, GetNextHighestWithSameDigits(val));

  val = 3971;
  printf("\nNextHighest(%d) = %d\n", val, GetNextHighestWithSameDigits(val));

  val = 83971;
  printf("\nNextHighest(%d) = %d\n", val, GetNextHighestWithSameDigits(val));

  val = 54321;
  printf("\nNextHighest(%d) = %d\n", val, GetNextHighestWithSameDigits(val));

  val = 1543;
  printf("\nNextHighest(%d) = %d\n", val, GetNextHighestWithSameDigits(val));

  val = 5643;
  printf("\nNextHighest(%d) = %d\n", val, GetNextHighestWithSameDigits(val));

  val = 405321;
  printf("\nNextHighest(%d) = %d\n", val, GetNextHighestWithSameDigits(val));

  val = 28634102;
  printf("\nNextHighest(%d) = %d\n", val, GetNextHighestWithSameDigits(val));

  val = 2864310;
  printf("\nNextHighest(%d) = %d\n", val, GetNextHighestWithSameDigits(val));

  val = 37723971;
  printf("\nNextHighest(%d) = %d\n", val, GetNextHighestWithSameDigits(val));

  return 0;
}

int GetNextHighestWithSameDigits(int inputValue)
{
  const int MaxDigitCount = 32;
  int errorCode;
  int inputDigitCount;
  int iFlip, nTemp, iSort;
  int outputValue;
  int i, j;

  digit *pInputDigits = NULL;

  pInputDigits = (digit *) malloc(MaxDigitCount * sizeof(digit));
  if (NULL == pInputDigits)
  {
    printf("\nERROR: Insufficient memory!");
    errorCode = -1;
    goto Exit;
  }

  // Get individual digits
  //
  inputDigitCount = 0;
  while (inputValue > 0)
  {
    pInputDigits[inputDigitCount++] = inputValue % 10;
    inputValue = inputValue / 10;
  }

  for (i = 0; i < (inputDigitCount >> 1); i++)
  {
    nTemp = pInputDigits[i];
    pInputDigits[i] = pInputDigits[inputDigitCount - i - 1];
    pInputDigits[inputDigitCount - i - 1] = nTemp;
  }

  if (inputDigitCount <= 0)
  {
    printf("\nERROR: Invalid input value!");
    errorCode = -2;
    goto Exit;
  }
  
  if (inputDigitCount < 1)
  {
    errorCode = 0; // Nothing 
    goto Exit;
  }

#ifdef DEBUG_PRINT
  printf("\nDEBUG : Digits = ");
  for (i = 0; i < inputDigitCount; i++)
  {
    printf("%d, ", pInputDigits[i]);
  }
#endif

  // Find first flip-over in increaseing sort order 
  // from right to left scan of number
  // 
  iFlip = -1;
  for (i = inputDigitCount-1; i > 0; i--)
  {
    if (pInputDigits[i] > pInputDigits[i-1])
    {
        iFlip = i;
        break;
    }
  }

  if (iFlip <= 0)
  {
    printf("\nERROR: No next higher value, this is the highest!");
    errorCode = -3;
    goto Exit;
  }

#ifdef DEBUG_PRINT
  printf("\nDEBUG : FlipOver = %d", pInputDigits[iFlip]);
#endif

  // Find the next highest element than the flip-over left digit
  //
  iSort = iFlip;
  for (i = iFlip + 1; i < inputDigitCount; i++)
  {
    if ((pInputDigits[iFlip-1] < pInputDigits[i]) &&
        (pInputDigits[i] < pInputDigits[iSort]))
    {
      iSort = i;
    }
  }

  // Swap the 'Next Highest' with flip-point left digit
  //
  nTemp = pInputDigits[iFlip-1];
  pInputDigits[iFlip-1] = pInputDigits[iSort];
  pInputDigits[iSort] = nTemp;

#ifdef DEBUG_PRINT
  printf("\nDEBUG : Digits (@Flip) = ");
  for (i = 0; i < inputDigitCount; i++)
  {
    printf("%d, ", pInputDigits[i]);
  }
#endif

  // Sort the digits from flip-point onwards
  // NOTE: Quick bubble sort (can be optimized)
  //
  for (i = iFlip; i < inputDigitCount; i++)
  {
    for (iSort = i, j = i+1; j < inputDigitCount; j++)
    {
      if (pInputDigits[iSort] > pInputDigits[j])
      {
        iSort = j;
      }
    }

    nTemp = pInputDigits[i];
    pInputDigits[i] = pInputDigits[iSort];
    pInputDigits[iSort] = nTemp;
  }

  // Construct the number back from the digits
  //
  outputValue = 0;
  for (i = 0; i < inputDigitCount; i++)
  {
    outputValue = outputValue * 10  + pInputDigits[i];
  }
  errorCode = 0;

Exit:

  if (NULL != pInputDigits)
  {
    free(pInputDigits);
  }
  
  return errorCode < 0 ? errorCode : outputValue;  
}

DEBUG : Digits = 1, 2, 3, 4, 5, 
DEBUG : FlipOver = 5
DEBUG : Digits (@Flip) = 1, 2, 3, 5, 4, 
NextHighest(12345) = 12354

DEBUG : Digits = 1, 3, 4, 8, 3, 
DEBUG : FlipOver = 8
DEBUG : Digits (@Flip) = 1, 3, 8, 4, 3, 
NextHighest(13483) = 13834

DEBUG : Digits = 3, 9, 7, 1, 
DEBUG : FlipOver = 9
DEBUG : Digits (@Flip) = 7, 9, 3, 1, 
NextHighest(3971) = 7139

DEBUG : Digits = 8, 3, 9, 7, 1, 
DEBUG : FlipOver = 9
DEBUG : Digits (@Flip) = 8, 7, 9, 3, 1, 
NextHighest(83971) = 87139

DEBUG : Digits = 5, 4, 3, 2, 1, 
ERROR: No next higher value, this is the highest!
NextHighest(54321) = -3

DEBUG : Digits = 1, 5, 4, 3, 
DEBUG : FlipOver = 5
DEBUG : Digits (@Flip) = 3, 5, 4, 1, 
NextHighest(1543) = 3145

DEBUG : Digits = 5, 6, 4, 3, 
DEBUG : FlipOver = 6
DEBUG : Digits (@Flip) = 6, 5, 4, 3, 
NextHighest(5643) = 6345

DEBUG : Digits = 4, 0, 5, 3, 2, 1, 
DEBUG : FlipOver = 5
DEBUG : Digits (@Flip) = 4, 1, 5, 3, 2, 0, 
NextHighest(405321) = 410235

DEBUG : Digits = 2, 8, 6, 3, 4, 1, 0, 2, 
DEBUG : FlipOver = 2
DEBUG : Digits (@Flip) = 2, 8, 6, 3, 4, 1, 2, 0, 
NextHighest(28634102) = 28634120

DEBUG : Digits = 2, 8, 6, 4, 3, 1, 0, 
DEBUG : FlipOver = 8
DEBUG : Digits (@Flip) = 3, 8, 6, 4, 2, 1, 0, 
NextHighest(2864310) = 3012468

DEBUG : Digits = 3, 7, 7, 2, 3, 9, 7, 1, 
DEBUG : FlipOver = 9
DEBUG : Digits (@Flip) = 3, 7, 7, 2, 7, 9, 3, 1, 
NextHighest(37723971) = 37727139