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. Sorting
  4. Lily's Homework
  5. Discussions

Lily's Homework

Sort by

recency

|

272 Discussions

|

  • quote_unquote
     + 0 comments
    /*
 * Complete the 'lilysHomework' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts INTEGER_ARRAY arr as parameter.
 */

void _print(const vector<int>& v) {
    for (auto e: v) { cout << e << " "; }
    cout << endl;
}

int _count(vector<int>& rx) {
    int n = rx.size();
    int i = 0;
    int j;
    int count = 0;
    while (i < n) {
        while ((j = rx[i]) != i) {
            swap(rx[i], rx[j]);
            count++;
        }
        i++;
    }
    return count;
}

int lilysHomework(vector<int> arr) {
    int n = arr.size();
    // _print(arr);

    vector<int> ix(n);
    iota(ix.begin(), ix.end(), 0);
    // _print(ix);    
    sort(ix.begin(), ix.end(), [&arr](int i, int j) { return arr[i] < arr[j]; });
    // _print(ix);

    vector<int> rx(n);  // rank
    for (size_t i = 0; i < n; ++i) { rx[ix[i]] = i; }
    // _print(rx);

    vector<int> rrx(n); // reversed rank
    for (size_t i = 0; i < n; ++i) { rrx[i] = n - 1 - rx[i]; }
    // _print(rrx);
    
    int c1 = _count(rx);
    int c2 = _count(rrx);
    
    return min(c1, c2);
}

  • 2k23_cs2313825
     + 0 comments

    simple c++ code with function

    int getswaps(unordered_map& d) { int swap = 0; for (auto& pair : d) { int x = pair.first; int y = pair.second; while (x != y) { swap++; d[x] = d[y]; d[y] = y; y = d[x]; } } return swap; } int lilysHomework(vector arr) { vector arrs = arr; sort(arrs.begin(), arrs.end()); unordered_map d1, d2;

    for (size_t i = 0; i < arr.size(); i++) {
    d1[arr[i]] = arrs[i];
    d2[arr[i]] = arrs[arr.size() - 1 - i];
}

return min(getswaps(d1), getswaps(d2));

    }

  • kbssj1
     + 0 comments

    javascript

    function lilysHomework(arr) {

    let sorted = arr.slice().sort((a, b) => a - b);
    let arr2 = arr.slice();
    let check = {};
    let check2 = {};
    let ans = 0;
    let ans2 = 0;
    for (let i=0;i<sorted.length;++i) {
        check[sorted[i]] = i;
    }
    for (let i=0;i<sorted.length;++i) {
        check2[sorted[i]] = sorted.length-1-i;
    }

    for(let i=0;i<arr.length;) {
        if (check[arr[i]] != i) {
            let t = arr[i];
            let t_i = check[arr[i]];
            arr[i] = arr[check[arr[i]]];
            arr[t_i] = t;
            ++ans;
        } else {
            ++i;
        }    
    }
    
    for(let i=arr2.length - 1;i>0;) {
        if (check2[arr2[i]] != i) {
            let t = arr2[i];
            let t_i = check2[arr2[i]];
            arr2[i] = arr2[check2[arr2[i]]];
            arr2[t_i] = t;
            ++ans2;
        } else {
            --i;
        }    
    }
    
    return ans < ans2 ? ans : ans2;
}

  • kalbertalbert121
     + 0 comments

    Sort the Array Track Cycles Count Swaps = (cycle length - 1) I run the test array [3,4,2,5,1] ->output 4, but the expected answer is 2,why?

    def lilysHomework(arr): # Write your code here # Create a list of tuples where each tuple is (element, original_index) n = len(arr) arr_with_indices = [(arr[i], i) for i in range(n)]

    # Sort the array by the element values
arr_with_indices.sort(key=lambda x: x[0])

# To track visited elements
visited = [False] * n
swaps = 0

for i in range(n):
    # If the element is already visited or already in the correct position, skip it
    if visited[i] or arr_with_indices[i][1] == i:
        continue

    # Start a new cycle
    cycle_size = 0
    j = i
    while not visited[j]:
        visited[j] = True
        j = arr_with_indices[j][1]  # Move to the next element in the cycle
        cycle_size += 1

    # If there is a cycle of size `k`, it takes `k - 1` swaps to sort the cycle
    if cycle_size > 1:
        swaps += cycle_size - 1

return swaps

  • djiloumnov
     + 0 comments

    Solution in JS: function getNumberSwaps(arr, arrMap, sortedArr) { let numberOfSwaps = 0; for (let i = 0; i < sortedArr.length; i++) { if (sortedArr[i] !== arr[i]) { const tmp = arr[i]; const idxSource = arrMap[sortedArr[i]];

            arr[i] = arr[idxSource];
        arr[idxSource] = tmp;

        arrMap[tmp] = idxSource;
        arrMap[sortedArr[i]] = i;

        numberOfSwaps++;
    }
}

return numberOfSwaps;

    }

    function lilysHomework(arr) { const ascArr = arr.toSorted((a, b) => a - b); const descArr = arr.toSorted((a, b) => b - a);

    const arrMap = {};
arr.forEach((num, idx) => {
    arrMap[num] = idx
});
return Math.min(getNumberSwaps([...arr], { ...arrMap }, ascArr), getNumberSwaps(arr, arrMap, descArr));

    }

    `