import java.io.*;
import java.util.*;
public class TestClass {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int arraySize = sc.nextInt();
int[]numArray = new int[arraySize];
for(int i = 0;i<arraySize;i++){
numArray[i] = sc.nextInt();
}
Arrays.sort(numArray);
int count = 1;
int currentToy=numArray[0];
for(int i = 1;i<numArray.length;i++){
if(numArray[i]>currentToy+4){
count++;
currentToy=numArray[i];
}
}
System.out.println(count);
}
}
- Problem Description
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 <= 10^5
0 <= wi <= 10^4, where i belongs to [1,N]
- Test Case 1
Input (stdin)5
1 2 3 17 10
Expected Output3
- Test Case 2
Input (stdin)4
1 2 3 17
Expected Output2
This comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDelete#include
ReplyDelete#include
#include
#include
int main()
{
int min,n,i,x,z,j,k,a[100000]={0};
scanf("%d",&n);
for(i=0;ia[j] && a[j]!=-1)
{
min = a[j];
}
}
x = min;
//printf("%d\n",min);
z++;
for(j=0;j= x && a[j] <= x+4)
{
a[j] = -1;
i = -1;
}
}
}
printf("%d",z);
return 0;
}
#include
ReplyDelete#include
using namespace std;
int w[100000];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> w[i];
sort(w, w + n);
int ans = 1, prev = w[0];
for (int i = 1; i < n; i++)
if (w[i] - prev > 4)
prev = w[i], ans++;
cout << ans << endl;
return 0;
}