Given an array of denominations, how many combinations of coins to sum total cents
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

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

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

  2. #2
    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[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
    If a post helped you dont forget to "Rate This Post"

    My Article: Capturing Windows Regardless of Their Z-Order

    Cheers

  3. #3
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,265

    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. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  4. #4
    Join Date
    Aug 2013
    Posts
    55

    Re: Given a number, find the next higher number

    Quote Originally Posted by android16 View Post
    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
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center