# Given an array of denominations, how many combinations of coins to sum total cents

• April 15th, 2014, 10:04 AM
android16
Given a number, find the next higher number
Came across this algorithm question:
Given a number, find the next higher number which has the exact same set of digits as the original number. For example: given 12478 return 12748.

It doesn't seem to be working. I'm missing something somewhere....

Code:

```public int findNextBig(int input  )  {       //Step 1: split the whole number to a list for individual digital  1358642->[2,4,6,8,5,3,1]     // this step is O(n)     int digitalLevel=input;     List<Integer> orgNumbersList=new ArrayList<Integer>()  ;     do {         Integer nInt = new Integer(digitalLevel % 10);         orgNumbersList.add(nInt);         digitalLevel=(int) (digitalLevel/10  )  ;     } while( digitalLevel >0)    ;     int len= orgNumbersList.size();     int [] orgNumbers=new int[len]  ;     for(int i=0;i<len;i++){         orgNumbers[i ]  =  orgNumbersList.get(i).intValue();     }     //step 2 find the first digital less than the digital right to it     // this step is O(n)     int firstLessPointer=1;     while(firstLessPointer<len&&(orgNumbers[firstLessPointer]>orgNumbers[ firstLessPointer-1 ])){         firstLessPointer++;     }     if(firstLessPointer==len-1&&orgNumbers[len-1]>=orgNumbers[len-2]){         //all number is in sorted order like 4321, no answer for it, return original         return input;     }     //when step 2 step finished, firstLessPointer  pointing to number 5     //step 3 fristLessPointer found, need to find  to  first number less than it  from low digital in the number     //This step is O(n)     int justBiggerPointer=  0 ;     while(justBiggerPointer<firstLessPointer&& orgNumbers[justBiggerPointer]<orgNumbers[firstLessPointer]){         justBiggerPointer++;     }     //when step 3 finished, justBiggerPointer  pointing to 6     //step 4 swap the elements  of justBiggerPointer and firstLessPointer .     // This  is O(1) operation  for swap   int tmp=  orgNumbers[firstLessPointer] ;     orgNumbers[firstLessPointer]=  orgNumbers[justBiggerPointer]  ;     orgNumbers[justBiggerPointer]=tmp ;     // when step 4 finished, the list looks like        [2,4,5,8,6,3,1]    the digital in the list before     // firstLessPointer is already sorted in our previous operation     // we can return result from this list  but  in a differrent way     int result=0;     int i=0;     int lowPointer=firstLessPointer;     //the following pick number from list from  the position just before firstLessPointer, here is 8 -> 5 -> 4 -> 2     //This Operation is O(n)     while(lowPointer>0)        {         result+= orgNumbers[--lowPointer]* Math.pow(10,i);         i++;     }     //the following pick number from list  from position firstLessPointer     //This Operation is O(n)     while(firstLessPointer<len)        {         result+ orgNumbers[firstLessPointer++ ]* Math.pow(10,i);         i++;     }     return  result; }```
• April 17th, 2014, 04:05 AM
golanshahar
Re: Given a number, find the next higher number
in the example you gave the next big number after 12478 is 12487

you can do something simple with ASCII - its not the best option and not fully debugged - its just to give you the idea

Code:

```        int Number = 12478;         char szNumber[256]={0};         char szNewNumer[256]={0};         itoa(Number, szNumber ,10);         int CntNewNumber = strlen(szNumber)-1;         bool Found = false;         for (int i =strlen(szNumber)-1; i >=0; i--)         {                 if ( !Found && szNumber[i] > szNumber[i-1]  )                 {                         szNewNumer[CntNewNubmer-1] = szNumber[i];                         szNewNumer[CntNewNubmer] = szNumber[i-1];                         CntNewNumer-=2;                         i--;                         Found= true;                         continue;                 }                 szNewNumer[CntNewNumber--] = szNumber[i];         }         int NewNumber = atoi(szNewNumer);```
Cheers
• April 17th, 2014, 07:46 AM
2kaud
Re: Given an array of denominations, how many combinations of coins to sum total cent
Another way of doing this is to generate all the permutations of the number and then return the one after. One way of doing this in c++ is
Code:

```#include <iostream> #include <algorithm> #include <string> #include <vector> using namespace std; int findNextBig(int num); int main() { int num;         cout << "Enter number: ";         cin >> num;         cout << "Next highest is: " << findNextBig(num);         return 0; } int findNextBig(int num) { string        text(to_string(num)),         org(text); vector<string> vstr;         sort(text.begin(), text.end());         do vstr.push_back(text);         while (next_permutation(text.begin(), text.end())); vector<string>::iterator got = find(vstr.begin(), vstr.end(), org);         return stoi(*(got + ((got + 1) != vstr.end()))); }```
The vector vstr will have all the permutations of the number in ascending order.
• April 17th, 2014, 08:13 AM
zizz
Re: Given a number, find the next higher number
Quote:

Originally Posted by android16
It doesn't seem to be working. I'm missing something somewhere....

I don't fancy working on someone else's code so I did my own implementation (according to the program development principle of Stepwise Refinement).

I think I came up with the same algorithm as you did:

1. Scan the number from the right and extract digits one by one.
2. Find the first digit that is smaller than the digit before. (note how the extracted digits appear in sorted order).
3. Then exchange this digit with the smallest bigger digit among the extracted digits. (note that this doesn't break the sorting)
4. Finally put the extracted digits back onto the number in reverse order.

The algorithm stops the first time it encounters a digit that is smaller than the previous digit. If digits appear with equal probability the expectation for this event is only a few couple of digits (2.22 if I got it right). In any case the complexity is dependent on the stochastic properties of the random sequence of digits and not the number of digits. That is the algorithm is O(1) rather than O(N).

Code:

```int firstbigger(int N) {         std::vector<int> v;         v.push_back(0); // make room for one digit         int d = N%10;         int n = N/10;         while (n > 0) { // extract digits from n from the right                 v.push_back(d);                 int t = d;                 d = n%10;                 n = n/10;                 if (d < t) { // d is first digit smaller than previous digit                         for (int i=1; i<int(v.size()); ++i) {                                 if (v[i] > d) { // first extracted digit bigger than d                                         v[0] = v[i]; // swap in                                         v[i] = d;                                         for (int j : v) n = n*10 + j; // add digits back on n in reverse                                         return n; // smallest bigger number                                 }                         }                 }         }         return N; // no bigger number exists, or number is negative }```