Given N * M rectangular park having N rows and M columns, each cell of the park is a square of unit area and boundaries between the cells is called hex and a sprinkler can be placed in the middle of the hex. The task is to find the minimum number of sprinklers required to water the entire park.
Examples:
Input: N = 3 M = 3
Output: 5
Explanation:
For the first two columns 3 sprinklers are required and for last column we are bound to use 2 sprinklers to water the last column.Input: N = 5 M = 3
Output: 8
Explanation:
For the first two columns 5 sprinklers are required and for last column we are bound to use 3 sprinklers to water the last column.
Approach:
- After making some observation one thing can be point out i.e for every two column, N sprinkler are required because we can placed them in between of two columns.
- If M is even, then clearly N* (M / 2) sprinklers are required.
- But if M is odd then solution for M – 1 column can be computed using even column formula, and for last column add ( N + 1) / 2 sprinkler to water the last column irrespective of N is odd or even.
C++
// C++ program to find the// minimum number sprinklers// required to water the park.#include <iostream>using namespace std;typedef long long int ll;// Function to find the// minimum number sprinklers// required to water the park.void solve(int N, int M){ // General requirements of // sprinklers ll ans = (N) * (M / 2); // if M is odd then add // one additional sprinklers if (M % 2 == 1) { ans += (N + 1) / 2; } cout << ans << endl;}// Driver codeint main(){ int N, M; N = 5; M = 3; solve(N, M);} |
Java
// Java program to find minimum// number sprinklers required// to cover the parkclass GFG{ // Function to find the minimum// number sprinklers required// to water the park.public static int solve(int n, int m){ // General requirements of sprinklers int ans = n * (m / 2); // If M is odd then add one // additional sprinklers if (m % 2 == 1) { ans += (n + 1) / 2; } return ans;}// Driver codepublic static void main(String args[]){ int N = 5; int M = 3; System.out.println(solve(N, M));}}// This code is contributed by grand_master |
Python3
# Python3 program to find the# minimum number sprinklers# required to water the park.# Function to find the# minimum number sprinklers# required to water the park.def solve(N, M) : # General requirements of # sprinklers ans = int((N) * int(M / 2)) # if M is odd then add # one additional sprinklers if (M % 2 == 1): ans += int((N + 1) / 2) print(ans)# Driver codeN = 5M = 3solve(N, M)# This code is contributed by yatinagg |
C#
// C# program to find minimum// number sprinklers required// to cover the parkusing System;class GFG{ // Function to find the minimum// number sprinklers required// to water the park.public static int solve(int n, int m){ // General requirements of sprinklers int ans = n * (m / 2); // If M is odd then add one // additional sprinklers if (m % 2 == 1) { ans += (n + 1) / 2; } return ans;}// Driver codepublic static void Main(String []args){ int N = 5; int M = 3; Console.WriteLine(solve(N, M));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program to find the// minimum number sprinklers// required to water the park.// Function to find the// minimum number sprinklers// required to water the park.function solve(N, M){ // General requirements of // sprinklers var ans = (N) * parseInt((M / 2)); // if M is odd then add // one additional sprinklers if (M % 2 == 1) { ans += parseInt((N + 1) / 2); } document.write(ans);}// Driver code var N, M; N = 5; M = 3; solve(N, M);// This code is contributed by SURENDRA_GANGWAR.</script> |
Output:
8
Time complexity: O(1)
Auxiliary space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
