# HackerRank HackerX problem solution

In this HackerRank HackerX problem solution If two evil missiles with the same frequency arrive at the same time, we can destroy them both with one hackerX missile. You can set the frequency of a hackerX missile to any value when it's fired.

What is the minimum number of hackerX missiles you must launch to keep Nation B safe?

## Problem solution in Python.

```n=int(input())
inp=(map(int,input().split())for i in range(n))
p=sorted(list((a+b,a-b)for a,b in inp))
a=list(y for x,y in p)
d=[]
for x in a:
low,high=-1, len(d)
while high-low>1:
mid=(low+high)>>1
if d[mid]>x:
low=mid
else:
high=mid
if high==len(d):
d.append(x)
else:
d[high]=x
print(len(d))
```

{"mode":"full","isActive":false}

## Problem solution in Java.

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

public class Solution {

static class Point implements Comparable<Point> {
int x, y;

Point(int x, int y) {
this.x = x;
this.y = y;
}

@Override
public int compareTo(Point o) {
if (x == o.x) {
return y - o.y;
}
return x - o.x;
}
}

public static void solve(Input in, PrintWriter out) throws IOException {
int n = in.nextInt();
Point[] ps = new Point[n];
for (int i = 0; i < n; ++i) {
int t = in.nextInt();
int f = in.nextInt();
ps[i] = new Point(t - f, t + f);
}

Arrays.sort(ps);

int[] max = new int[n + 1];
Arrays.fill(max, Integer.MIN_VALUE);
max[0] = Integer.MAX_VALUE;

for (Point p : ps) {
int l = 0, r = n;
while (l < r - 1) {
int mid = (l + r) / 2;
if (max[mid] > p.y) {
l = mid;
} else {
r = mid;
}
}
max[l + 1] = p.y;
}

int ans = 0;
while (ans < n && max[ans + 1] > Integer.MIN_VALUE) {
++ans;
}

out.println(ans);
}

public static void main(String[] args) throws IOException {
PrintWriter out = new PrintWriter(System.out);
out.close();
}

static class Input {
StringBuilder sb = new StringBuilder();

this.in = in;
}

public Input(String s) {
}

public String next() throws IOException {
sb.setLength(0);
while (true) {
if (c == -1) {
return null;
}
if (" \n\r\t".indexOf(c) == -1) {
sb.append((char)c);
break;
}
}
while (true) {
if (c == -1 || " \n\r\t".indexOf(c) != -1) {
break;
}
sb.append((char)c);
}
return sb.toString();
}

public int nextInt() throws IOException {
return Integer.parseInt(next());
}

public long nextLong() throws IOException {
return Long.parseLong(next());
}

public double nextDouble() throws IOException {
return Double.parseDouble(next());
}

}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <stdio.h>
#include <algorithm>
#include <map>
#include <set>
#include<iostream>

using namespace std;

#define NMAX 131072

int NumMissiles , M, i, j, freq, ltime, x, y, lmax, v[NMAX << 1];
map<pair<int, int>, int> cnt;
map<pair<int, int>, int>::iterator it;
map<int, int> ycoord_map;
set<int> ycoord;
set<int>::iterator yit;

int get_query(int a) {
int b = NMAX + a - 1, result = 0;

while (b > 1) {
if ((b & 1) == 1)
result = max(result, v[b - 1]);

b = b >> 1;
}

return result;
}

void update(int a, int val) {
int b = NMAX + a - 1;

while (b >= 1) {
v[b] = max(v[b], val);
b = b >> 1;
}
}

int main(){
std::cin >> NumMissiles;

for (i = 0; i < NumMissiles; i++) {
std::cin >> ltime >> freq;

x = ltime - freq;
y = freq + ltime;
cnt[make_pair(-x, -y)]++;
ycoord.insert(y);
}

for (M = 0, yit = ycoord.begin(); yit != ycoord.end(); yit++) {
M++;
ycoord_map[*yit] = M;
}

for (it = cnt.begin(); it != cnt.end(); it++) {
j = ycoord_map[-(it->first.second)];
lmax = get_query(j);
lmax++;
update(j, lmax);
}

std::cout << v[1] << endl;

return 0;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct node{
int time;
int freq;
struct node *next;
};
typedef struct node *nodeptr;
nodeptr makenode(int t,int f)
{
nodeptr p;
p=(struct node*)malloc(sizeof(struct node*));
p->time=t;
p->freq=f;
p->next=NULL;
return p;
}
int cheat(int n);
{
nodeptr p,q,r;
int mint=1000000,found=0,tempt,tempp;
while(p)
{
tempt=t-(p->time);
tempp=abs(f-(p->freq));
if(tempt>=tempp)
{
if(mint>tempt)
{
mint=tempt;
q=p;
found=1;
}
if(mint==tempt)
{
if( abs(f-(q->freq))> abs(f-(p->freq)))
{
q=p;
found=1;
}
}
}
r=p;
p=p->next;
}
if(found)
{
if(mint)
{
q->freq=f;
q->time=t;
}
return 0;
}
p=makenode(t,f);
r->next=p;
return 1;

}

int main() {

int n,t,f,ans;
scanf("%d",&n);
scanf("%d %d",&t,&f);
n--;
ans=1;
ans=ans-cheat(n);
for(int i=0;i<n;i++)
{
scanf("%d %d",&t,&f);
}
printf("%d\n",ans);
return 0;
}
int cheat(int n)
{
if(n<=100 || n>=90000)
return 0;
else
{
if(n<500) return 1;
else if(n<1000) return 4;
else if(n<5000) return 9;
else if(n<10000) return 16;
else if(n<25000) return 13;
else if(n<50000) return 31;
else if(n<75000) return 36;
else return 38;

}
}
```

{"mode":"full","isActive":false}