Skip to content
  • Home
  • Contact Us
  • About Us
  • Privacy Policy
  • DMCA
  • Linkedin
  • Pinterest
  • Facebook
thecscience

TheCScience

TheCScience is a blog that publishes daily tutorials and guides on engineering subjects and everything that related to computer science and technology

  • Home
  • Human values
  • Microprocessor
  • Digital communication
  • Linux
  • outsystems guide
  • Toggle search form
HackerRank HackerX Problem Solution

HackerRank HackerX Problem Solution

Posted on May 25, 2023May 25, 2023 By Yashwant Parihar No Comments on HackerRank HackerX Problem Solution

In this post, we will solve HackerRank HackerX Problem Solution.

Update: A slight modification in the problem statement (see below)

Evil Nation A is angry and plans to launch N guided-missiles at the peaceful Nation B in an attempt to wipe out all of Nation B’s people. Nation A’s missile i will arrive in nation B at time ti. Missile i communicates with its headquarters by unique radio signals with a frequency equal to fi. Can you help the peaceful Nation B survive by building a defensive system that will stop the missiles dead in the sky?

Defensive system:

The only way to defend Nation B from the attacking missile is by counter attacking them with a hackerX missile. You have a lot of hackerX missiles and each one of them has its own radio frequency. An individual hackerX missile can destroy Evil Nation A’s attacking missile if the radio frequency of both of the missiles match. Each hackerX missile can be used an indefinite number of times. Its invincible and doesn’t get destroyed in the collision.

The good news is you can adjust the frequency of the hackerX missile to match the evil missiles’ frequency. When changing the hackerX missile’s initial frequency fA to the new defending frequency fB, you will need \|fB – fA\| units of time to do.

Each hackerX missile can only destroy one of Nation A’s missile at a time. So if two evil missiles with same frequency arrive at the same time, you need at least two hackerX missiles with the same frequency as the evil missiles to avoid damage.

If two evil missles with 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 its fired.

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

Input Format:
The first line contains a single integer N denoting the number of missiles.
This is followed by N lines each containing two integers ti and fi denoting the time & frequency of the ith missile.

Output Format:
A single integer denoting the minimum number of hackerX missiles you need to defend the nation.

Constraints:
1 <= N <= 100000
0 <= ti <= 100000
0 <= fi <= 100000
t1 <= t2 <= … <= tN

Sample Input #00

4
1 1
2 2
3 1
5 1

Sample Output #00

1

Explanation #00

A HackerX missile is launched at t = 1 with a frequency f = 1, and destroys the first missile. It re-tunes its frequency to f = 2 in 1 unit of time, and destroys the missile that is going to hit Nation B at t = 2. It re-tunes its frequency back to 1 in 1 unit of time and destroys the missile that is going to hit the nation at t = 3. It is relaunched at t = 5 with f = 1 and destroys the missile that is going to hit nation B at t = 5. Hence, you need only 1 HackerX to protect nation B.

Sample Input #01

4
1 1
2 3
3 1
5 1

Sample Output #01

2

Explanation #01

Destroy 1 missile at t = 1, f = 1. now at t = 2, there is a missile with frequency 3. The launched missile takes 2 units of time to destroy this, hence we need a new hackerX missile to destroy this one. The first hackerX missile can destroy the 3rd missile which has the same frequency as itself. The same hackerX missile destroys the missile that is hitting its city at t = 5. Thus, we need atleast 2 hackerX missiles.

HackerRank HackerX Problem Solution
HackerRank HackerX Problem Solution

Table of Contents

  • HackerX C Solution
  • HackerX C++ Solution
  • HackerX C Sharp Solution
  • HackerX Java Solution
  • HackerX JavaScript Solution
  • HackerX Python Solution

HackerX C Solution

 #include <stdio.h>


void conquer(int a[],int b[],int low,int mid,int high){

    int i,m,k,l,temp[100002],temp2[100002];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){
        if(a[l]<=a[m]){
             temp[i]=a[l];
             temp2[i]=b[l];
             l++;
         }
         else{
             temp[i]=a[m];
             temp2[i]=b[m];
             m++;
         }
         i++;
    }
    if(l>mid){
         for(k=m;k<=high;k++){
             temp[i]=a[k];
             temp2[i]=b[k];
             i++;
         }
    }
    else{
         for(k=l;k<=mid;k++){
             temp[i]=a[k];
             temp2[i]=b[k];
             i++;
         }
    }

    for(k=low;k<=high;k++){
         a[k]=temp[k];
         b[k]=temp2[k];
    }
}
void divide(int a[],int b[],int low,int high){

    int mid;

    if(low<high){
         mid=(low+high)/2;
         divide(a,b,low,mid);
         divide(a,b,mid+1,high);
         conquer(a,b,low,mid,high);
    }
}
int main()
{
    int t,at[100002],af[100002],i,j,countmissile=1,saved,bt[1002],bf[1002],timechange,freqchange,k1;
    int z1[100002],z2[100002];
    int ans[100002];
    
    scanf("%d", &t);
    for(i=0;i<t;i++)
    {
        scanf("%d %d",&at[i],&af[i]);
        z1[i]=at[i]-af[i];
        z2[i]=at[i]+af[i];
    }
    divide(z1,z2,0,t-1);
    for(i=0;i<t;i++)
    {
        int var= z2[i-1];
        int low = 0;
        int high = countmissile-1;
        while(low <= high)
        {
            int mid = (low + high )/2;
            if(ans[mid]>var)
                low = mid+1;
            else
                high  = mid -1;
        }
        if(countmissile <= low)
        {
            ans[countmissile] = var;
            countmissile++;
        }
        else{
            ans[low] = var;
        }

    }
    printf("%d", countmissile);
}

HackerX C++ Solution

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

using namespace std;

#define NMAX 131072

int N, M, i, j, f, t, 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() {
    scanf("%d", &N);

    for (i = 0; i < N; i++) {
        scanf("%d %d", &t, &f);
        x = t - f;
        y = f + t;
        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);
    }

    printf("%d\n", v[1]);

    return 0;
}

HackerX C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'missileDefend' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts 2D_INTEGER_ARRAY missiles as parameter.
     */

    public static int missileDefend(List<List<int>> missiles)
    {
        var points = new List<Point>();
            foreach (List<int> missile in missiles)
            {
                points.Add(new Point(missile[0] - missile[1], missile[0] + missile[1]));
            }

            var sortedArray = points.OrderBy(o => o.X).ThenBy(o => o.Y).Select(s=>s.Y).ToList();

            var list = new SortedSet<int>();
            list.Add(sortedArray[0]);

            for (int i = 1; i < sortedArray.Count; i++)
            {
                var y = sortedArray[i];
                var set = list.GetViewBetween(0,y);
                if (set.Count != 0)
                {
                    list.Remove(set.Last());
                }
                list.Add(y);
            }

            return list.Count();
    }
    
    public class Point {
        public int X {get; set;}
        public int Y {get; set;}
        public Point(int x, int y)
        {
            X = x;
            Y = y;
        }
    }
}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int n = Convert.ToInt32(Console.ReadLine().Trim());

        List<List<int>> missiles = new List<List<int>>();

        for (int i = 0; i < n; i++)
        {
            missiles.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(missilesTemp => Convert.ToInt32(missilesTemp)).ToList());
        }

        int result = Result.missileDefend(missiles);

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

HackerX Java Solution

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);
        solve(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
        out.close();
    }

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

        public Input(BufferedReader in) {
            this.in = in;
        }

        public Input(String s) {
            this.in = new BufferedReader(new StringReader(s));
        }

        public String next() throws IOException {
            sb.setLength(0);
            while (true) {
                int c = in.read();
                if (c == -1) {
                    return null;
                }
                if (" \n\r\t".indexOf(c) == -1) {
                    sb.append((char)c);
                    break;
                }
            }
            while (true) {
                int c = in.read();
                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());
        }
    
    }
}

HackerX JavaScript Solution

function lowerBound(array, bound) {
  var first = 0;
  var count = array.length;

  while (count > 0) {
    var step = Math.floor(count / 2);
    var it = first + step;
    if (array[it] < bound) {
      first = it + 1;
      count -= step + 1;
    } else {
      count = step;
    }
  }

  return first;
}

function processData(input) {
  var lines = input.split('\n');
  var missiles = [];
  var hackers = [];
  var N = parseInt(lines.shift(), 10);

  while (N--) {
    var tf = lines.shift().split(' ');
    var t = parseInt(tf.shift(), 10);
    var f = parseInt(tf.shift(), 10);
    missiles.push([t+f, t-f]);
    hackers.push(Number.MAX_VALUE);
    max = t;
  }

  missiles.sort(function (a, b) {
    return b[0] - a[0] || b[1] - a[1];
  }).forEach(function (missile, i) {
    //console.log(missile, lowerBound(hackers, missile[1]), hackers[lowerBound(hackers, missile[1])], missile[1]);
    hackers[lowerBound(hackers, missile[1])] = missile[1];
  });
  //console.log(hackers);

  console.log(lowerBound(hackers, Number.MAX_VALUE));
} 


process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

HackerX Python Solution

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))
c, C#, C++, HackerRank Solutions, java, javascript, python Tags:C, cpp, CSharp, Hackerrank Solutions, java, javascript, python

Post navigation

Previous Post: HackerRank Hacker Country Problem Solution
Next Post: HackerRank Huarongdao Problem Solution

Related Posts

HackerRank The Love-Letter Mystery Problem Solution HackerRank The Love-Letter Mystery Solution c
HackerRank Larry's Array Problem Solution HackerRank Larry’s Array Problem Solution c
HackerRank How Many Substrings? Problem Solution HackerRank How Many Substrings? Solution C#
HackerRank Build a Palindrome Problem Solution HackerRank Build a Palindrome Problem Solution c
HackerRank Bear and Steady Gene Problem Solution HackerRank Bear and Steady Gene Solution c
HackerRank Closest Numbers Problem Solution HackerRank Closest Numbers Problem Solution c

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick Your Subject
Human Values

Copyright © 2023 TheCScience.

Powered by PressBook Grid Blogs theme