Finding maximum number that can be composed out of a set of integers using greedy algorithm

user_19576917 0
Viewed 168

I am trying to compose the largest possible number out of a set of integers. The code only works if the input is single digits otherwise it gives me wrong answer. for example, if the input is 2, 21 it gives me 212 instead of 221. I have tried to edit the code but I got stuck. I had an idea to convert any number the user enters to digits i.e 210 -> 2, 1, 0. but I don't know how to implement it.

int IsGreaterOrEqual(int n1, int n2)
{
    
}

void swap(int* xp, int* yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void selectionSort(int arr[], int n)
{
    int i, j, min_idx;

    // One by one move boundary of unsorted subarray
    for (i = 0; i < n - 1; i++) {

        // Find the minimum element in unsorted array
        min_idx = i;
        for (j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;

        // Swap the found minimum element
        // with the first element
        swap(&arr[min_idx], &arr[i]);
    }
}

int main()
{
    int n;   //number of elements
    scanf("%d", &n);
    int ints[n], sol[n];
    int size = sizeof(ints)/sizeof(ints[0]); 

    for(int i = 0; i < n; i++){   //taking the inputs from the user
        scanf("%d", &ints[i]);
    }

    ints[n] = selectionSort(ints, size);   //sort the array in ascending order


    for(int i = n-1; i >= 0; i--){   //here is where I am stuck
        
    }
}

I am was going to use IsGreaterOrEqual function to append the 2 numbers forward and backward and return the greatest number. for example, append 2 and 21 -> 221 and 212. How can I edit the code to work for any set of positive integers?

c algorithm
1 Answers

At first you produce undefined behaviour by accessing an array beyond its bounds with ints[n] = ... – not sure why you return a value at all, as you sort in place anyway. What would be the semantics of that return value? Rather change to void and just drop that assignment.

Same occurs on reading ints[i-1] for i being 0...

Then you try sorting sorting the input by their integral value (you scan as ints). The problem with: Consider the two values 2 and 11 – obviously the smaller one needs to come first; however if you consider 22 and 1 now the larger one needs to come first. This just as obviously reveals that you cannot sort that way. Instead you need to sort the numbers lexicographically by their textual representation.

For this purpose read the numbers as C strings into appropriate arrays; make sure you prevent undefined behaviour by reading beyond the array bounds, i.e. provide maximum length to scanf (e.g. scanf("%31s", array) for a 32 character array) or maybe prefer fgets or getline together with strtok over scanf.

You optionally might want to add a check if those strings really only contain digits by iterating over them and checking with is_digit (to be fully correct convert the input characters to unsigned char for, covering characters with values > 127 on char being signed!).

Now you can simply compare these strings via strcmp – however you need special handling for one string being a prefix of the other one, in worst case recursively (remainder or old prefix again being a new prefix of the other one...).

This can lead to code e.g. as follows:

int less(char const* x, char const*y)
{
    size_t nx = strlen(x);
    size_t ny = strlen(y);
    size_t min = nx < ny ? nx : ny;
    int factor = 1;
    for(;;)
    {
        int cmp = strncmp(x, y, min);
        if(cmp != 0)
        {
            return factor * cmp < 0;
        }
        if(nx == ny)
        {
            return 0; // equal -> not less
        }
        if(nx < ny)
        {
            // need to change roles!
            size_t ntmp = nx;
            nx = ny;
            ny = ntmp;
            char const* tmp = x;
            x = y;
            y = tmp;
            factor = -factor;
        }
        nx -= ny;
        x += ny;
    }
}

Demonstration on godbolt...

For the final main you might scan into a 2D character array and then create an additional array of pointers into the 2D array (you can swap pointers more efficiently) or read in all input at once into a large 1D character array and tokenise with strtok, again placing the resulting pointers into another array (I personally prefer the latter approach, actually I'd do the tokenising on my own on checking the digits, if doing so at all). Now sort the pointer array in place in descending order using above comparison and just output the array entries one after another – no need for any second array (sol in your case)...

Final recommendation: Try to understand, if need be, ask a new question or leave a comment and then re-implement on your own. This is the way you learn something from. If you instead prefer just to copy 'n' paste the ready to use code – feel free to do so, I don't mind. Nothing learnt then, but not my problem ;)

user_13123820
Related