HackerRank : Week of Code 27 – Tailor Shop

By | December 20, 2016

Tailor Shop

Jaime the Tailor’s new customer wants to add n  distinct clusters to her dress, where each cluster is filled with a distinct number of buttons of a certain color. Other words no two clusters should have the same color buttons.

The customer also has specific ideas about how much she wants to pay for each cluster in that for some cluster .She wants to pay at least ai dollars. Addition, she wants each cluster to contain a distinct number of buttons. And, finally, she wants to minimize her total cost.

Jaime stocks an infinite number of buttons in an infinite number colors at his shop, and each button costs p dollars. Given n, p, and the amount of money that the customer wants to pay for each respective cluster, help Jaime by finding and printing a long integer denoting the minimum number of buttons he can use to satisfy her request.

Input Format

The first line contains two space-separated integers denoting the respective values of n and p.
The second line contains n space-separated integers where each integer i  denotes the value of ai  (i.e., the minimum amount of money she wants to spend on cluster i).

Constraints

 1<=n,p,ai<=10^5

Output Format

Print a single long integer denoting the minimum number of buttons required for Jaime to satisfy his customer’s request.

Sample Input 0

3 2
4 6 6

Sample Output 0

9

Explanation 0
Let’s say we use red buttons for the first cluster, green buttons for the second cluster, and yellow buttons for the third cluster:

  1. The customer’s requested minimum cost for the first cluster is dollars, and Jaime needs at least two buttons priced at dollars apiece to satisfy this cost. Jaime chooses two red buttons such that the cost of the first cluster is dollars.
  2. The customer’s requested minimum cost for the second cluster is dollars, and Jaime needs at least three buttons priced at dollars apiece to satisfy this minimum cost. Jaime chooses three green buttons such that the cost of the second cluster is dollars.
  3. The customer’s requested minimum cost for the third cluster is dollars, and Jaime needs at least three buttons priced at dollars apiece to satisfy this minimum cost. Jaime’s second cluster already contains three buttons, so he chooses four yellow buttons such that the cost of the third cluster is dollars.

Each cluster has a distinct number of buttons, so we print a long integer denoting the total number of buttons required, which is .

Girl demand.png

Sample Input 1

2 3
4 5

Sample Output 1

5

Explanation 1
Let’s say we use red buttons for the first cluster and green buttons for the second cluster.

  1. The customer’s requested minimum cost for the first cluster is dollars. And Jaime needs at least two buttons priced at dollars apiece to satisfy this cost. Jaime chooses two red buttons such that the cost of the first cluster is dollars.
  2. The customer’s requested minimum cost for the second is dollars. And Jaime needs at least two buttons priced at dollars apiece to satisfy this minimum cost. Jaime chooses three green buttons such that the cost of the second cluster is dollars.

Each cluster has a distinct number of buttons, so we print a long integer denoting the total number of buttons required, which is .

Girl demand(2).png

Source :  Hackerrank

Solution

I am using HashSet to keep track of count of buttons. 
If I get same count then I increase the count variable and store in the set.

On the first day, its having TLE in 2 test cases.

Comment to get suggestions.
Code:


import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Solution {

    public static void main(String[] args) {
      	Scanner scan= new Scanner(System.in);
		int n=scan.nextInt();
		int p=scan.nextInt();
		
		int a[]= new int[n];
		
		for(int i=0;i<n;i++)
			a[i]=scan.nextInt();
		
		Set quantity= new HashSet();
		int count=0;
		
		for(int i=0;i<n;i++)
		{
			int tempQuantity= a[i]/p;
			count=0;
			
			if(a[i]%p==0)
			{
			//	System.out.println("Yes");
				count=tempQuantity;
			}
			else
			{
				count=tempQuantity+1;
			}
			if(i==0)
				quantity.add(count);
			else
			{
			//	System.out.println("Hi "+ count);
				
				while(quantity.contains(count))
				{
					count++;
				}
				quantity.add(count);
			//	System.out.println(quantity);
			}
			
		//	System.out.println("count is "+count);
			
		}
		
		//System.out.println(quantity);
		int finalcount=0;
		
		for (Integer integer : quantity) {
		
			finalcount= finalcount+integer;
		}
		System.out.println(finalcount);
    }
}