Given an integer array A[] of size N and integer k. For a fixed value p, choose an index i (1 ≤ i ≤ n) and assign A[i] = max(0, A[i] − p), this counts as one operation, and the task is to find the smallest value of p such that all the elements of the array A[] become 0 in at most k operations.
Examples:
Input: N = 4, k = 6, A[] = {3, 5, 1, 4}
Output: 3
Explanation: By choosing p = 3 we can make all elements equal to zero in Atmost 6 operationsInput: N = 3, k = 2, A[] = {1, 0, 1}
Output: 1
Explanation: By choosing p = 1 we can make all elements equal to zero in almost 2 operations
Approach 1: This can be solved with the following idea:
For a given value of p, we can reduce any number (let’s say X) to zero in at most ceil(X/p) operations. As the value of p increases the number of operations to make array elements zero will reduce. So, this is a monotonic function so we can solve this question by the binary search for an answer. So we can determine the minimum value of p for which the number of operations will not exceed m operation in O(N*log(max(A[i])). For a given value of p we can go over the array elements and count the number of operations by using the formula ceil(A[i]/p).
Steps involved in the implementation of code:
- Initialize low and high pointers as 0 and 1e18.
- Find the mid value of these two pointers and see whether for this mid we can make all elements 0 in k or less than k operations.
- If, yes then assign p as mid and make high = mid – 1.
- Else, assign low = mid + 1.
Below is the code for the above approach:
C++
// C++ Implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find how many operations
// this p will take
bool check(int p, int N, int A[], int k)
{
int i = 0;
int operations = 0;
while (i < N) {
// if A[i] = 0
if (!A[i]) {
i++;
continue;
}
// if p = 0
if (!p) {
return false;
}
operations += (A[i] + p - 1) / p;
i++;
}
return operations <= k;
}
// Function to find lowest value of p
void lowestP(int N, int A[], int k)
{
int low = 0;
int high = INT_MAX;
int p;
while (low <= high) {
int mid = low + (high - low) / 2;
// Check for operations required
if (check(mid, N, A, k)) {
p = mid;
high = mid - 1;
}
else {
low = mid + 1;
}
}
// Return minimum operations
cout << p;
}
// Driver code
int main()
{
int N = 4;
int A[] = { 3, 5, 1, 4 };
int k = 6;
// Function call
lowestP(N, A, k);
return 0;
}
Java
// Java Implementation of the above approach
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
// Function to find how many operations
// this p will take
static boolean check(int p, int N, int A[], int k)
{
int i = 0;
int operations = 0;
while (i < N) {
// if A[i] = 0
if (A[i] == 0) {
i++;
continue;
}
// if p = 0
if (p == 0) {
return false;
}
operations += (A[i] + p - 1) / p;
i++;
}
return operations <= k;
}
// Function to find lowest value of p
static void lowestP(int N, int A[], int k)
{
int low = 0;
int high = Integer.MAX_VALUE;
int p = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
// Check for operations required
if (check(mid, N, A, k)) {
p = mid;
high = mid - 1;
}
else {
low = mid + 1;
}
}
// Return minimum operations
System.out.print(p);
}
// Driver code
public
static void main(String[] args)
{
int N = 4;
int A[] = { 3, 5, 1, 4 };
int k = 6;
// Function call
lowestP(N, A, k);
}
}
Python3
# Python3 code for the above approach
import sys
# Function to find how many operations
# this p will take
def check(p, N, A, k):
i = 0
operations = 0
while i < N:
# if A[i] = 0
if not A[i]:
i += 1
continue
# if p = 0
if not p:
return False
operations += (A[i] + p - 1) // p
i += 1
return operations <= k
# Function to find lowest value of p
def lowestP(N, A, k):
low = 0
high = sys.maxsize
p = 0
while (low <= high):
mid = low + (high - low) // 2
# Check for operations required
if check(mid, N, A, k):
p = mid
high = mid - 1
else:
low = mid + 1
# Return minimum operations
print(p)
# Driver code
if __name__ == '__main__':
N = 4
A = [3, 5, 1, 4]
k = 6
# Function call
lowestP(N, A, k)
C#
// C# Implementation of the above approach
using System;
public class GFG
{
// Function to find how many operations
// this p will take
public static bool Check(int p, int N, int[] A, int k)
{
int i = 0;
int operations = 0;
while (i < N)
{
// if A[i] = 0
if (A[i] == 0)
{
i++;
continue;
}
// if p = 0
if (p == 0)
{
return false;
}
operations += (A[i] + p - 1) / p;
i++;
}
return operations <= k;
}
// Function to find lowest value of p
public static void LowestP(int N, int[] A, int k)
{
int low = 0;
int high = int.MaxValue;
int res = 0;
while (low <= high)
{
int mid = low + (high - low) / 2;
// Check for operations required
if (Check(mid, N, A, k))
{
res = mid;
high = mid - 1;
}
else
{
low = mid + 1;
}
}
// Return minimum operations
Console.WriteLine(res);
}
public static void Main()
{
int N = 4;
int[] A = { 3, 5, 1, 4 };
int k = 6;
// Function call
LowestP(N, A, k);
}
}
Javascript
// JavaScript Implementation of the above approach
// Function to find how many operations
// this p will take
function check(p, N, A, k)
{
let i = 0;
let operations = 0;
while (i < N) {
// if A[i] = 0
if (!A[i]) {
i++;
continue;
}
// if p = 0
if (!p) {
return false;
}
operations += Math.ceil(A[i] / p);
i++;
}
return operations <= k;
}
// Function to find lowest value of p
function lowestP(N, A, k)
{
let low = 0;
let high = Number.MAX_SAFE_INTEGER;
let p;
while (low <= high) {
let mid = low + Math.floor((high - low) / 2);
// Check for operations required
if (check(mid, N, A, k)) {
p = mid;
high = mid - 1;
}
else {
low = mid + 1;
}
}
// Return minimum operations
console.log(p);
}
// Driver code
let N = 4;
let A = [ 3, 5, 1, 4 ];
let k = 6;
// Function call
lowestP(N, A, k);
Output
3
Time Complexity: O(N*log(max(A[i])).
Auxiliary Space:O(N)
Approach 2: Using binary search to find the minimum value of p
- First, we can calculate the maximum element in the array, let’s call it max_val. Then, we can iterate over all possible values of p starting from 1 to max_val. For each value of p, we can calculate the number of operations required to make all elements in the array equal to 0 using the formula ceil(A[i]/p) and summing over all elements in the array.
- Once we have calculated the number of operations for a particular value of p, we can compare it with the given value of m. If the number of operations required is less than or equal to m, we update the answer and continue to check for smaller values of p.
- The idea behind this approach is that as we increase the value of p, the number of operations required to make all elements equal to 0 decreases. So, we can start with a small value of p and gradually increase it until we find the minimum value of p that satisfies the given condition.
Below is the code for the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
// Considering same input set of values
int n = 4;
int k = 6;
int A[] = { 3, 5, 1, 4 };
int max_val = 0;
for (int i = 0; i < n; i++) {
max_val = max(max_val, A[i]);
}
int ans = INT_MAX;
for (int p = 1; p <= max_val; p++) {
int num_ops = 0;
for (int i = 0; i < n; i++) {
num_ops += ceil((double)A[i] / p);
}
if (num_ops <= k) {
ans = min(ans, p);
}
}
cout << ans << endl;
return 0;
}
Java
// java program to implement the above approach
import java.util.*;
public class Main {
public static void main(String[] args)
{
// Considering same input set of values
int n = 4;
int k = 6;
int[] A = { 3, 5, 1, 4 };
int max_val = 0;
for (int i = 0; i < n; i++) {
max_val = Math.max(max_val, A[i]);
}
int ans = Integer.MAX_VALUE;
for (int p = 1; p <= max_val; p++) {
int num_ops = 0;
for (int i = 0; i < n; i++) {
num_ops += Math.ceil((double)A[i] / p);
}
if (num_ops <= k) {
ans = Math.min(ans, p);
}
}
System.out.println(ans);
}
}
// This code is contributed by Chetan Bargal
Python3
import math
# Considering same input set of values
n = 4
k = 6
A = [3, 5, 1, 4]
max_val = 0
for i in range(n):
max_val = max(max_val, A[i])
ans = float('inf')
for p in range(1, max_val+1):
num_ops = 0
for i in range(n):
num_ops += math.ceil(A[i] / p)
if num_ops <= k:
ans = min(ans, p)
print(ans)
C#
using System;
class Program {
static void Main(string[] args) {
// Considering same input set of values
int n = 4;
int k = 6;
int[] A = { 3, 5, 1, 4 };
int max_val = 0;
for (int i = 0; i < n; i++) {
max_val = Math.Max(max_val, A[i]);
}
int ans = int.MaxValue;
for (int p = 1; p <= max_val; p++) {
int num_ops = 0;
for (int i = 0; i < n; i++) {
num_ops += (int)Math.Ceiling((double)A[i] / p);
}
if (num_ops <= k) {
ans = Math.Min(ans, p);
}
}
Console.WriteLine(ans);
}
}
Javascript
// Considering same input set of values
const n = 4;
const k = 6;
const A = [3, 5, 1, 4];
let max_val = 0;
for (let i = 0; i < n; i++) {
max_val = Math.max(max_val, A[i]);
}
let ans = Infinity;
for (let p = 1; p <= max_val; p++) {
let num_ops = 0;
for (let i = 0; i < n; i++) {
num_ops += Math.ceil(A[i] / p);
}
if (num_ops <= k) {
ans = Math.min(ans, p);
}
}
console.log(ans);
Output
3
Time Complexity: O(N*max_val)
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!
Share your thoughts in the comments
