Count maximum number of giants that can be destroyed before they reach the city

Given two arrays dist[] and speed[] consisting of N integers, where dist[i] is the initial distance of the i^th giant from the city and speed[i] is the speed of the i^th giant. One giant can be eliminated every minute. Therefore, at any time t, at most t giants can be killed. If more giants are able to reach the city in time t, then the game is over. The task is to find the maximum number of giants that can be eliminated before losing, or N if all of the giants can be eliminated before they reach the city.

Examples:

Input: dist[] = [1, 3, 4], speed[] = [1, 1, 1]
Output: 3
Explanation: At the start of minute 0, the distances of the  giants are [1, 3, 4]. The first giant is eliminated.
At the start of 1st minute, the distances of the giants are [X, 2, 3]. No giant is eliminated.
At the start of 2nd minute, the distances of the giants are [X, 1, 2]. The second giant is eliminated.
At the start of 3rd minute, the distances of the giants are [X, X, 1]. The third  giant is eliminated.
All 3  giants can be eliminated.

Input: dist[] = [1, 1, 2, 3], speed[] = [1, 1, 1, 1]
Output: 1

Approach: The idea is to use the greedy approach to solve the problem. Find the time for each giant to come into the city and try to destroy the giant with the least possible time of approaching. Follow the steps below to solve the problem:

• Initialize a vector timezone[] to store the times.
• Iterate over the range [0, N] using the variable i and perform the following steps:
  • Push the value of dist[i]/speed[i] into the vector timezone[].
• Sort the vector timezone[] in ascending order.
• Initialize the variables curr_time as 0 to store the current time and killcount as 0 to store the number of giants killed.
• Iterate over the range [0, N] using the variable i and perform the following steps:
  • If timezone[i] is less than curr_time, then break the loop.
  • Else, increase the count of curr_time and killcount by 1.
• After performing the above steps, return the value of killcount as the answer.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h> using namespace std; int eliminateMaximum(int dist[], int N,                      int speed[]) {                    vector<double> timezone;     for (int i = 0; i < N; i++) {         timezone.push_back((double)dist[i]                            / (double)speed[i]);     }          sort(timezone.begin(), timezone.end());          int Curr_time = 0;          int killcount = 0;     for (auto i : timezone) {         if (i <= Curr_time) {                          break;         }         else {             Curr_time++;             killcount++;         }     }     return killcount; } int main() {          int dist[] = { 1, 3, 4 };     int N = sizeof(dist) / sizeof(dist[0]);     int speed[] = { 1, 1, 1 };     int M = sizeof(speed) / sizeof(speed[0]);          cout << eliminateMaximum(dist, N, speed); }

Javascript

<script>                                    function eliminateMaximum(dist, N, speed)         {                                                              let timezone = [];             for (let i = 0; i < N; i++) {                 timezone.push(dist[i] / speed[i]);             }                          timezone.sort(function (a, b) { return a - b; });                          let Curr_time = 0;                          let killcount = 0;             for (let i of timezone) {                 if (i <= Curr_time) {                                          break;                 }                 else {                     Curr_time++;                     killcount++;                 }             }             return killcount;         }                           let dist = [1, 3, 4];         let N = dist.length;         let speed = [1, 1, 1];         let M = speed.length;                  document.write(eliminateMaximum(dist, N, speed));     </script>

 
 

Output: 

3

Time Complexity: O(N * log(N))
Auxiliary Space: O(N)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets