Cerinta completa

Lauren has a chart of distinct projected prices for a house over the next several years. She must buy the house in one year and sell it in another, and she must do so at a loss. She wants to minimize her financial loss.

Example

Her minimum loss is incurred by purchasing in year at and reselling in year at . Return .

Function Description

Complete the minimumLoss function in the editor below.

minimumLoss has the following parameter(s):

  • int price[n]: home prices at each year

Returns

  • int: the minimum loss possible

Input Format

The first line contains an integer , the number of years of house data.
The second line contains space-separated long integers that describe each .

Constraints

  • All the prices are distinct.
  • A valid answer exists.

Subtasks

  • for of the maximum score.

Sample Input 0

3
5 10 3

Sample Output 0

2

Explanation 0

Lauren buys the house in year at and sells it in year at for a minimal loss of .

Sample Input 1

5
20 7 8 2 5

Sample Output 1

2

Explanation 1

Lauren buys the house in year at and sells it in year at for a minimal loss of .

Limbajul de programare folosit: java8

Cod:

//Problem: https://www.hackerrank.com/challenges/minimum-loss
//Java 8
/*

Initial Thoughts: We can sort the array to reduce the number of comparisons since
                  we know that the absolute difference is always smallest between
                  adjacent elements in a sorted array. Then because we have the 
                  stipulation that we must buy the house before we can sell it
                  we should verify that the buy price we are using is a price
                  that occurred in a year prior to the sell price year. We can
                  accomplish this by using a map that will be at most size n and
                  will store distinct key,value pairs where the key is the price
                  and the value is the year.
                  
Time Complexity: O(n log(n)) //We must sort the input array
Space Complexity: O(n) //We use a map to store the price,year pairs
*/
import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        long[] prices = new long[n];
        HashMap<Long,Integer> indices = new HashMap<>();

        //Populate prices array with the input
        for(int i = 0; i < n; i++){
            prices[i] = input.nextLong();
            indices.put(prices[i],i);
        }

        Arrays.sort(prices);//Performs a double pivot quicksort and sorts ascending

        Long minimumLoss = Long.MAX_VALUE;

        //Iterate from end to start
        for(int i = n-1; i >0; i--){
            //Make sure it is a smaller loss
            if(prices[i]-prices[i-1] < minimumLoss){
                //Verify if the pair is a valid transaction
                if(indices.get(prices[i]) < indices.get(prices[i-1]))
                    minimumLoss = prices[i]-prices[i-1];
            }
        }

        System.out.println(minimumLoss);

    }
}

Scor obtinut: 1.0

Submission ID: 464602837

Link challenge: https://www.hackerrank.com/challenges/minimum-loss/problem

Minimum Loss