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;
}
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
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.
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
}
