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

Sort by

recency

|

2111 Discussions

|

  • maluisamrok
     + 0 comments

    hey!! for Java 8 my solution was this and I´m very happy with it.

    List<Integer> response = new ArrayList<>();
    
    do {
         response.add(arr.size());
         int min =Collections.min(arr);
         arr.removeIf(n-> (n == min));
        
        }
    while (arr.size()>=1);

   
   
   return response;

  • claudelounou75
     + 0 comments

    My C code with good optimisation 😁😎🐦‍🔥

     void swap(int* xp,int* yp){
    const int temp = *xp;
    *xp = *yp;
    *yp = temp;
 }
 
 int partition(int arr[],int low,int high){
    const int pivot = arr[high];
    int i = low - 1;
    
    for(int j = low;j < high;j++){
        if(arr[j] <= pivot){
            i++;
            swap(&arr[i],&arr[j]);
        }
    }
    swap(&arr[i+1],&arr[high]);
    return i + 1;
 }
 
 void quickSort(int arr[],int low,int high){
    if(low < high){
        int pi = partition(arr,low,high);
        quickSort(arr,low,pi - 1);
        quickSort(arr,pi + 1,high);
    }
 }
 
 int minValue(int arr[],int size){
    int min = 0;
    for(int i = 0; i < size;i++){
        if(size <= arr[i] && arr[i] > 0){
            min = arr[i];
        }
    }
    return min;
 }
 
int* cutTheSticks(int arr_count, int* arr, int* result_count) {
    quickSort(arr, 0, arr_count - 1);

    int size = 0;
    int* result = (int*)malloc(arr_count * sizeof(int));
    result[size++] = arr_count;

    int current_length = arr_count;
    int min = arr[0];
    
    for (int i = 0; i < arr_count;) {
        int count = 0;
        while (i < arr_count && arr[i] == min) {
            count++;
            i++;
        }
        current_length -= count;
        if (current_length > 0) {
            result[size++] = current_length;
            if (i < arr_count) {
                min = arr[i];
            }
        }
    }

    result = (int*)realloc(result, size * sizeof(int));
    *result_count = size;

    return result;
}

  • facumanj
     + 0 comments

    Hi everyone, my solution not passing test 5 & 6. Any clue why? Thanks in advance.

        public static List<Integer> cutTheSticks(List<Integer> arr) {
    // Write your code here
        List<Integer> results = new ArrayList<>();
        
        Collections.sort(arr);
        
        results.add(arr.size());
        
        for (int i=1; i < arr.size(); i++) {
            if (arr.get(i) != arr.get(i-1)) {
              results.add(arr.size()-i);     
            }
        }
         
        return results;
    }

  • galrub
     + 0 comments
    public static List<Integer> cutTheSticks(List<Integer> arr) {
        arr = arr.stream().sorted().collect(Collectors.toList());
        List<Integer> res = new ArrayList<>();
        while(arr.size() > 0) {
            res.add(arr.size());
            final int shortest = arr.get(0);
            while (!arr.isEmpty() && arr.get(0) == shortest)
                arr.remove(0);
            arr = arr.stream().map(v -> v - shortest).collect(Collectors.toList());
        }
        return res;
    }

  • voronin_ilia
     + 0 comments

    C++ Solution with recursion:

    int recurse(vector<int>& r, vector<int> arr, int min) {
  int res = 0;
  vector<int> v;
  
  r.push_back(arr.size());
  
  for(auto& a : arr) {
    if ((a - min) > 0) {
      v.push_back(a - min);
      res++;
    }
  }
  min = *min_element(v.begin(),v.end());
  if(res > 0)
    recurse(r, v, min);
    
  return res;
}

vector<int> cutTheSticks(vector<int> arr) {
  vector<int> res;

  int min = *min_element(arr.begin(),arr.end());
  recurse(res, arr, min);
  
  return res;
}