Cerinta completa

Whenever George asks Lily to hang out, she’s busy doing homework. George wants to help her finish it faster, but he’s in over his head! Can you help George understand Lily’s homework so she can hang out with him?

Consider an array of distinct integers, . George can swap any two elements of the array any number of times. An array is beautiful if the sum of among is minimal.

Given the array , determine and return the minimum number of swaps that should be performed in order to make the array beautiful.

Example

One minimal array is . To get there, George performed the following swaps:

    Swap      Result
          [7, 15, 12, 3]
    3 7   [3, 15, 12, 7]
    7 15  [3, 7, 12, 15]

It took swaps to make the array beautiful. This is minimal among the choices of beautiful arrays possible.

Function Description

Complete the lilysHomework function in the editor below.

lilysHomework has the following parameter(s):

  • int arr[n]: an integer array

Returns

  • int: the minimum number of swaps required

Input Format

The first line contains a single integer, , the number of elements in .
The second line contains space-separated integers, .

Constraints

Sample Input

STDIN       Function
-----       --------
4           arr[]size n = 4
2 5 3 1     arr = [2, 5, 3, 1]

Sample Output

2

Explanation

Define to be the beautiful reordering of . The sum of the absolute values of differences between its adjacent elements is minimal among all permutations and only two swaps ( with and then with ) were performed.

Limbajul de programare folosit: java8

Cod:

//Problem: https://www.hackerrank.com/challenges/lilys-homework
//Java 8
/*
Initial Thoughts: We can compare a sorted array to the original
                  and just keep track of the differences. As we
                  go we will need to perform the swaps, becasue we
                  are not guranteed 1 swap will fix both elements.
                  We will do this on both a ascending sort and a
                  descending sort as both meet the minimal 
                  requirement
                  
Time Complexity: O(n log(n)) //We must sort the input
Space Complexity: O(n) //We store the input in an array
*/
import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        
        int sortedSwaps = 0;
        int[] homework = new int[n];
        Integer[] homeworkSorted = new Integer[n];
        Map<Integer,Integer> original = new HashMap<>();
        
        int sortedReverseSwaps = 0;    
        int[] homework2ndCopy = new int[n];        
        Map<Integer,Integer> original2ndCopy = new HashMap<>();
        
        //Initialize our arrays and maps
        for(int i = 0; i < n; i++)
        {
            homeworkSorted[i] = input.nextInt();
            homework[i] = homeworkSorted[i];
            homework2ndCopy[i] = homeworkSorted[i];
            original.put(homework[i],i);
            original2ndCopy.put(homework2ndCopy[i],i);
        }
            
        Arrays.sort(homeworkSorted);//Sort the input ascending
        
        for(int i = 0; i < n; i++)
        {
            if(homework[i] != homeworkSorted[i])
            {
                //swap the element from homework to the right position
                int tmp = homework[i];
                homework[i] = homework[original.get(homeworkSorted[i])];
                homework[original.get(homeworkSorted[i])] = tmp;
                //Update index after swap
                original.put(tmp,original.get(homeworkSorted[i]));
                sortedSwaps++;               
            }
        }
        
        Arrays.sort(homeworkSorted, Collections.reverseOrder());//Sort the input descending
        
        for(int i = 0; i < n; i++)
        {
            if(homework2ndCopy[i] != homeworkSorted[i])
            {
                //swap the element from homework to the right position
                int tmp = homework2ndCopy[i];
                homework2ndCopy[i] = homework2ndCopy[original.get(homeworkSorted[i])];
                homework2ndCopy[original2ndCopy.get(homeworkSorted[i])] = tmp;
                //Update index after swap
                original2ndCopy.put(tmp, original2ndCopy.get(homeworkSorted[i]));
                sortedReverseSwaps++;
            }
        }
        System.out.println(Math.min(sortedSwaps,sortedReverseSwaps));//Choose the smallest of the two possible smallest
    }
}

Scor obtinut: 1.0

Submission ID: 464602710

Link challenge: https://www.hackerrank.com/challenges/lilys-homework/problem

Lily’s Homework