We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Cut the sticks
  5. Discussions

Cut the sticks

  • doliatius
     + 0 comments

    I know, this is just a "remove min elements, add the new length of the array to the return array" problem but this is how it can be done in C. Welcome to relatively low level programming guys:

    int* cutTheSticks(int arr_count, int* arr, int* result_count) {
    *result_count = 0;
    int *ret = malloc(arr_count * sizeof(int));

    while (arr_count > 0) {
        int min = arr[0];
        for (int i = 1; i < arr_count; i++) {
            if (arr[i] < min) min = arr[i];
        }

        int count = 0;
        for (int i = 0; i < arr_count; i++) {
            if (arr[i] == min) count++;
        }
        
        ret[*result_count] = arr_count;
        (*result_count)++;

        int new_count = arr_count - count;
        int *new_arr = malloc(new_count * sizeof(int));
        int j = 0;
        for (int i = 0; i < arr_count; i++) {
            if (arr[i] != min) new_arr[j++] = arr[i];
        }
        free(arr);
        arr = new_arr;
        arr_count = new_count;
    }

    return ret;
}