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.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Lily's Homework
  5. Discussions

Lily's Homework

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 247 Discussions, By:

recency

Please Login in order to post a comment

  • cyliaengels
    3 weeks ago+ 0 comments
    def lilysHomework(arr):
        elements = [(value, index) for index, value in enumerate(arr)]
        sorted_elements = sorted(elements)
        index_map = {index: i for i, (_, index) in enumerate(sorted_elements)}
        asc_swaps = calculate_swaps(arr, index_map)
        sorted_elements = sorted(elements, reverse=True)
        index_map = {index: i for i, (_, index) in enumerate(sorted_elements)}
        desc_swaps = calculate_swaps(arr, index_map)
        return min(asc_swaps, desc_swaps)
    
    
    def calculate_swaps(arr, index_map):
        swaps = 0
        visited = [False] * len(arr)
    
        for i in range(len(arr)):
            if visited[i] or index_map[i] == i:
                continue
    
            cycle_size = 0
            j = i
    
            while not visited[j]:
                visited[j] = True
                j = index_map[j]
                cycle_size += 1
    
            if cycle_size > 0:
                swaps += cycle_size - 1
    
        return swaps
    
    0|
    Permalink
  • billslim0996
    2 months ago+ 1 comment

    hint: count the number of swap operation needed to sort the given array either in ascending or decenting order. return which one cost less.

    -1|
    Permalink
  • mineman1012221
    2 months ago+ 0 comments

    Here is the solution of Lily's Homework Click Here

    -2|
    Permalink
  • rejwan_azam_mon1
    4 months ago+ 0 comments

    Feel free to let me know if there's any issue in this C code.

    #define min(x, y) (((x) < (y)) ? (x) : (y))
    
    int comp(const void * a, const void * b){
        return *(int*)a-*(int*)b;
    }
    
    int no_of_swaps(int *arr,int arr_count){
        int *a = (int*)malloc(arr_count*sizeof(int));
        int* sort;
        int i,c=0;
        for(i=0;i<arr_count;i++){
            a[i] = arr[i];
        }
        qsort(a,arr_count,sizeof(int),comp);
        for(i=0;i<arr_count;i++){
            if(arr[i] != a[i]){
                c +=1;
                int j = i+1;
                while(arr[j] != a[i]){
                    j++;
                }
                
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        free(a);
        return c;
    }
    
    int lilysHomework(int arr_count, int* arr) {
         int *arr_copy = (int*)malloc(arr_count*sizeof(int));
        memcpy(arr_copy, arr, arr_count*sizeof(int));
        int normal_order, reverse_order;
        normal_order = no_of_swaps(arr_copy,arr_count);
        int* reversed_arr = (int*)malloc(arr_count*sizeof(int));
        for (int i = 0; i < arr_count; i++) {
            reversed_arr[i] = arr[arr_count - i - 1];
        }
        reverse_order = no_of_swaps(reversed_arr,arr_count);
        return min(normal_order,reverse_order);
    }
    
    0|
    Permalink
  • claudia_yao2012
    4 months ago+ 1 comment

    It takes me lots of time to solve this challenge, so I have to write something to share with you bothered by it:

    a. ascending and descending sequence of the data will influence the swap times. So your method needs to be called twice and then you choose the smaller swap times as your answer. b. Consider the small circles of data, which might affect the swap times. for example, 0>2, 2>1, 1>0, 3->4, 4>5, 5>3, totally there are 4 swaps, but my first try uses another simple method which gets 5 swaps and that is wrong.

    -2|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy