 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

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

1. Junior Member Join Date
Apr 2014
Posts
5

## 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);

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;

}```
Last edited by android16; April 16th, 2014 at 09:39 AM.  Reply With Quote

2. Elite Member Power Poster           Join Date
May 2005
Posts
4,954

## 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={0};
char szNewNumer={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  Reply With Quote

3. ## 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.
Last edited by 2kaud; April 17th, 2014 at 07:51 AM.  Reply With Quote

4. Banned Join Date
Aug 2013
Posts
55

## Re: Given a number, find the next higher number 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 = 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
}```
Last edited by zizz; April 19th, 2014 at 01:19 AM.  Reply With Quote

algorithm, recursion #### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
• 