Priyanka and Toys

Difficulty: Easy

Little Priyanka visited a kids' shop. There are N toys and their weight is represented by an array W=[w1,w2,…,wN]. Each toy costs 1 unit, and if she buys a toy with weight w′, then she can get all other toys whose weight lies between [w′,w′+4](both inclusive) free of cost.

Input Format

The first line contains an integer N i.e. number of toys.
Next line will contain N integers, w1,w2,…,wN, representing the weight array.

Output Format

Minimum units with which Priyanka could buy all of toys.

Constraints
1≤N≤105
0≤wi≤104,where i∈[1,N]

Sample Input

5
1 2 3 17 10

Sample Output

3

Explanation

She buys 1st toy with weight 1 for 1unit and gets 2nd and 3rd toy for free since their weight lies between [1,5]. And she has to buy last two toys separately

Runtime Analysis:

Given the following constraints:

1≤N≤105
0≤wi≤104,where i∈[1,N]

We know that in the worst case, we have to process 105 elements (Just reading in the input). The average processor (usually assumed to be 2GHz) can do 2 x 109  possible operations per second. However each line of code often takes more than 1 operation to perform, so we often estimate 2 x 108 operations per second (off by factor of 10), which means that, for a linear solution, we can execute our code within 1 second and is most likely a viable solution. However, anything more than linear will likely cause a timeout. O(n2) will take 1010  which will take about 50 seconds to compute. Typically,  Hacker rank contests have a 4 second time out for Java solutions, which means we need to write a O(n) solution.

Runtime: O(n)




Algorithmic Approach:

This question is a great beginning to learning the Greedy Algorithm. In this case, a simple Greedy Approach will suffice and solve the problem. Since Priyanka gets toys of the price [w, w+4] for free, we sort the array and traverse each element at a time. During each iteration, we keep track of the last element we "purchased" (curr) and if our current value is greater than curr + 4 (we need to "purchase" a new element), then we add to our count and update the last "purchased" value. 




Java Code: 

import java.io.*;
import java.util.*;

public class Solution{
 

 public static void main(String []args){
  Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
  int [] arr = new int[n];

  for(int i = 0; i < n; i ++){
   arr[i] = sc.nextInt();
  }

  Arrays.sort(arr);

  int count = 1;
  int currVal = arr[0];

  for(int i = 0; i < n; i++){
   if(arr[i] > currVal + 4){
    currVal = arr[i];
    count++;
   }
  }

  System.out.println(count);

 }
}