-
April 15th, 2014, 10:04 AM
#1
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;
}
Last edited by android16; April 16th, 2014 at 09:39 AM.
-
April 17th, 2014, 04:05 AM
#2
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
#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.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
April 17th, 2014, 08:13 AM
#4
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[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
}
Last edited by zizz; April 19th, 2014 at 01:19 AM.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|