Hackerrank Hackerland Radio Transmitters Solution

5 1
1 2 3 4 5

2

8 2
7 2 4 6 5 9 12 11 

3

import java.util.Scanner;
import java.util.Arrays;

public class Solution {
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);

		int n = in.nextInt();
		int k = in.nextInt();

		int[] p = new int[n];
		for (int i = 0; i < n; ++i) p[i] = in.nextInt();

		Arrays.sort(p);
	
		int uncover = 0;
		int lamp = -1;
		int count = 0;

		for (int i = 1; i < n; ++i){
			if (uncover <= lamp && p[i] - p[lamp] > k) uncover = i;
  
			if (uncover > lamp && p[i] - p[uncover] > k) {
				++count;
				lamp = i - 1;
				--i;
			}
		}

		if (lamp == -1 || p[n - 1] - p[lamp] > k) {
			++count;
			lamp = n - 1;
		}

		System.out.println(count);
	}
}

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    static int hackerlandRadioTransmitters(int[] x, int k) {
            Arrays.sort(x);
		 	int numOfTransmitters = 0;
		 	int i = 0;
		 	while (i < x.length) {
		 	    numOfTransmitters++;
		 	    int loc = x[i] + k;
		 	    while (i < x.length && x[i] <= loc) 
		 	    {
		 	    	i++;
			 	    
		 	    }	
		 	    loc = x[--i] + k;
		 	    while (i < x.length && x[i] <= loc)
		 	    {
		 	    	i++;
		 	    }
		 	}
		 	return numOfTransmitters;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] x = new int[n];
        for(int x_i = 0; x_i < n; x_i++){
            x[x_i] = in.nextInt();
        }
        int result = hackerlandRadioTransmitters(x, k);
        System.out.println(result);
        in.close();
    }
}

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    static int hackerlandRadioTransmitters(int[] x, int k, int n) {
        // Complete this function
        Arrays.sort(x);
        int numOfTransmitters = 0;
        int i = 0;

        while (i < n ) {
            numOfTransmitters++;
            int loc = x[i] + k;
            
            while (i < n && x[i] <= loc) i++;
            loc = x[--i] + k; 
            while (i < n && x[i] <= loc) i++;
        }
        
        return numOfTransmitters;

    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int[] x = new int[n];
        for(int x_i = 0; x_i < n; x_i++){
            x[x_i] = in.nextInt();
        }
        int result = hackerlandRadioTransmitters(x, k, n);
        System.out.println(result);
        in.close();
    }
}

n, k = map(int, input().split())
x = sorted(list(set(list(map(int, input().split())))))
n = len(x)

count, first_uncovered = 0, 0
while first_uncovered < n:
  i = first_uncovered
  while i < n and x[i] - x[first_uncovered] <= k:
    i += 1
  while first_uncovered < n and x[first_uncovered] - x[i - 1] <= k:
    first_uncovered += 1
  count += 1
print(count)

n, k = [int(i) for i in input().split()]
H = [0]*(10**5 + 1)
x = [int(i) for i in input().split()]
min_index = x[0]
max_index = x[0]
for i in x:
    H[i] = 1
    min_index = min(min_index, i)
    max_index = max(max_index, i)
r = 0
i = min_index
while(i <= max_index):
    r += 1
    j = i + k
    if (j <= max_index):
        while(H[j] != 1 and j > i):
                j -= 1
    i = j + k + 1
    while (i <= max_index and H[i] != 1):
        i += 1

print(r)
    

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the hackerlandRadioTransmitters function below.
def hackerlandRadioTransmitters(x, k):
    count=0
    i=0
    x.sort()
    n=len(x)
    while i<n:
        count=count+1
        loc=x[i]+k
        while i<n and x[i]<=loc:
            i=i+1
        loc=x[i-1]+k
        while i<n and x[i]<=loc:
            i=i+1
    return count
    


if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nk = input().split()

    n = int(nk[0])

    k = int(nk[1])

    x = list(map(int, input().rstrip().split()))

    result = hackerlandRadioTransmitters(x, k)

    fptr.write(str(result) + '\n')

    fptr.close()

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    int k;
    cin >> n >> k;
    vector<int> x(n);
    for(int x_i = 0;x_i < n;x_i++){
       cin >> x[x_i];
    }
    int i=0;
    sort(x.begin(),x.end());
    int count=0;
    int loc;
    while(i<n){
        count++;
        loc=x[i]+k;
        while(i<n && x[i]<=loc)
            i++;
        i--;
        loc=x[i]+k;
        while(i<n && x[i]<=loc)
            i++;
    }
    cout<<count;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;


int main(){
    int n;
    int k;
    cin >> n >> k;
    vector<int> a(n);
    for(int x_i = 0;x_i < n;x_i++){
       cin >> a[x_i];
    }
    
    sort(a.begin(),a.end());
    a.erase( unique( a.begin(), a.end() ), a.end() );
    
    int count=0;
    int i=0;
    while(i<a.size()){
        int x=lower_bound(a.begin(),a.end(),a[i]+k)-a.begin();
        if(a[x]!=a[i]+k)
            --x;
        
        ++count;
        int y= lower_bound(a.begin(),a.end(),a[x]+k)-a.begin();
        if(a[y]==a[x]+k)
            ++y;
       
        i=y;
    }
    cout<<count;
    return 0;
}

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;


int main(){
    int n;
    int k;
    cin >> n >> k;
    vector<int> x(n);
    for(int x_i = 0;x_i < n;x_i++){
       cin >> x[x_i];
    }
    sort(x.begin(),x.end());
    int i,j,l;
    i=0;
    int count=0;
    while(i<n){
        j=i;
        while((x[j]-x[i])<=k && j<n){
            j++;
        }
        l=j;
        count++;
        while(x[l]-x[j-1]<=k && l<n){
            l++;
        }
        i=l;
    }
    cout<<count<<endl;
    return 0;
}