/*ata Structures
Algorithms
Interview Preparation
Topic-wise Practice
C++
Java
Python
Competitive Programming
Machine Learning
Web Development
Puzzles
Project Ideas
GFG School
▲
Related Articles
Find the minimum possible health of the winning player
Minimum possible final health of the last monster in a game
Top 10 System Design Interview Questions and Answers
How to Crack System Design Round in Interviews?
Design Dropbox – A System Design Interview Question
Design Twitter – A System Design Interview Question
5 Common System Design Concepts for Interview Preparation
Getting Started with System Design
5 Tips to Crack Low-Level System Design Interviews
Design an online book reader system
Design a Logistics System
Design Snake Game
Design a Chess Game
Design a Hit Counter
How to design a tiny URL or URL shortener?
Sort an array of 0s, 1s and 2s
Sort an array of 0s, 1s and 2s (Simple Counting)
Segregate 0s and 1s in an array
Segregate Even and Odd numbers
Sort all even numbers in ascending order and then sort all odd numbers in descending order
Sort even-placed elements in increasing and odd-placed in decreasing order
Permute two arrays such that sum of every pair is greater or equal to K
Choose k array elements such that difference of maximum and minimum is minimized
Sort an array when two halves are sorted
Find pair with greatest product in array
Top 50 Array Coding Problems for Interviews
Recursion
Difference between BFS and DFS
Counting Sort
A* Search Algorithm
Minimum possible final health of the last monster in a game
Difficulty Level : Medium
Last Updated : 05 Aug, 2021
Given N monsters, each monster has initial health h[i] which is an integer. A monster is alive if its health is greater than 0. In each turn a random monster kills another random monster, the monster which is attacked, its health reduces by the amount of health of the attacking monster. This process is continued until a single monster is left. What will be the minimum possible health of the last remained monster. In others words, the task is to play the game in such a way that monster which is left in the end has the least possible health.
Examples:
Input: h[] = {2, 14, 28, 56}
Output: 2
When only the first monster keeps on attacking the remaining 3 monsters, the final health of the last monster will be 2, which is minimum.
Input: h[] = {7, 17, 9, 100, 25}
Output: 1
Input: h[] = {5, 5, 5}
Output: 5
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Approach: It can be observed from the problem that one has to find a certain value of health of the monster, let’s say k which can kill other monsters including self. Once this crucial observation is made problem becomes easy. Suppose we have two monsters with health h1 and h2, and let’s say h2 > h1. We can see that in a random choice, the optimal way would be to pick a monster with lower health and reduce the health of the other monster till its health becomes less than the health of the attacking monster. After that we will pick the second monster whose health has became less than h1 and the process w
*/// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the gcd of two numbers
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to return the minimum
// possible health for the monster
int solve(int* health, int n)
{
// gcd of first and second element
int currentgcd = gcd(health[0], health[1]);
// gcd for all subsequent elements
for (int i = 2; i < n; ++i) {
currentgcd = gcd(currentgcd, health[i]);
}
return currentgcd;
}
// Driver code
int main()
{
int health[] = { 1, 2, 6, 7 };
int n = sizeof(health) / sizeof(health[0]);
cout << solve(health, n);
return 0;
} Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}