# Minimum value of X such that sum of arr[i] – X raised to the power of brr[i] is less than or equal to K

Given an array **arr[]** and **brr[]** both consisting of **N** integers and a positive integer **K**, the task is to find the minimum value of **X** such that the sum of the maximum of **(arr[i] – X, 0) **raised to the power of **brr[i]** for all array elements **(arr[i], brr[i])** is **at most K**.

**Examples:**

Input:arr[] = {2, 1, 4, 3, 5} brr[] = { 4, 3, 2, 3, 1}, K = 12Output:2Explanation:

Consider the value of X as 2, then the value of the given expression is:

=> max(2 – 2, 0)^{4}+ max(1 – 2, 0)^{3}+ max(4 – 2, 0)^{2}+ max(3 – 2, 0)^{3 }+max(5 – 2, 0)^{1}

=> 0^{4 }+ 0^{3}+ 2^{2 }+ 1^{3}+ 3^{1}= 8 <= K(= 12).

Therefore, the resultant value of X is 2, which is minimum.

Input:arr[] = {2, 1, 4, 3, 5} brr[] = { 4, 3, 2, 3, 1}, K = 22Output:1

**Naive Approach:** The simplest approach to solve the given problem is to check for every value of **X** from **0** to the maximum element of the array and if there exists any value of **X** satisfying the given conditions, then print that value of **X** and break out of the loop.

**Time Complexity:** O(N*M), where, M is the *maximum element of the array**.***Auxiliary Space:** O(1)

**Efficient Approach:** The above approach can also be optimized by using Binary Search to find the value of **X** and if a particular value of **X** satisfies the above condition, then, all the greater values will also satisfy, therefore, then try to search for lower values. Follow the steps below to solve the problem:

- Define a function
**check(a[], b[], k, n, x):**- Initialize the variable
**sum**as**0**to calculate the desired sum from the array**arr[]**and**brr[].** - Iterate over the range
**[0, N]**using variable**i**and add the value of**pow(max(arr[i] – x, 0), brr[i])**to the variable**sum**. - If the value of
**sum**is less than equal to**K**, then, return**true**. Otherwise, return**false**.

- Initialize the variable
- Initialize the variables, say
**low**as**0**and**high**as maximum value of the array. - Iterate in a while loop till
**low**is less than**high**and perform the following steps:- Initialize the variable
**mid**as the average of**low**and**high**. - Check the value of
**mid**to see whether it satisfies the given conditions by calling the function**check(arr[], brr[], k, n, mid)**. - If the function
**check(arr[], brr[], n, k, mid)**returns**true**then, update the**high**to**mid**. Otherwise, update the value of**low**to**(mid + 1)**. - After completing the above steps, return the value of
**low**as the result from the function.

- Initialize the variable
- After performing the above steps, print the value of
**low**as the desired value of**X**as the answer.

Below is the implementation of the above approach:

## C++14

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to check if there exists an` `// X that satisfies the given conditions` `bool` `check(` `int` `a[], ` `int` `b[], ` `int` `k, ` `int` `n, ` `int` `x)` `{` ` ` `int` `sum = 0;` ` ` `// Find the required value of the` ` ` `// given expression` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `sum = sum + ` `pow` `(max(a[i] - x, 0), b[i]);` ` ` `}` ` ` `if` `(sum <= k)` ` ` `return` `true` `;` ` ` `else` ` ` `return` `false` `;` `}` `// Function to find the minimum value` `// of X using binary search.` `int` `findMin(` `int` `a[], ` `int` `b[], ` `int` `n, ` `int` `k)` `{` ` ` `// Boundaries of the Binary Search` ` ` `int` `l = 0, u = *max_element(a, a + n);` ` ` `while` `(l < u) {` ` ` `// Find the middle value` ` ` `int` `m = (l + u) / 2;` ` ` `// Check for the middle value` ` ` `if` `(check(a, b, k, n, m)) {` ` ` `// Update the upper` ` ` `u = m;` ` ` `}` ` ` `else` `{` ` ` `// Update the lower` ` ` `l = m + 1;` ` ` `}` ` ` `}` ` ` `return` `l;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `arr[] = { 2, 1, 4, 3, 5 };` ` ` `int` `brr[] = { 4, 3, 2, 3, 1 };` ` ` `int` `K = 12;` ` ` `int` `N = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `cout << findMin(arr, brr, N, K);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `class` `GFG{` ` ` `// Function to check if it is possible to` `// get desired result` `static` `boolean` `check(` `int` `a[], ` `int` `b[], ` `int` `k, ` `int` `x)` `{` ` ` `int` `sum = ` `0` `;` ` ` `for` `(` `int` `i = ` `0` `; i < a.length; i++)` ` ` `{` ` ` `sum = sum + (` `int` `)Math.pow(` ` ` `Math.max(a[i] - x, ` `0` `), b[i]);` ` ` `}` ` ` `if` `(sum <= k)` ` ` `return` `true` `;` ` ` `else` ` ` `return` `false` `;` `}` `// Function to find the minimum value` `// of X using binary search.` `static` `int` `findMin(` `int` `a[], ` `int` `b[], ` `int` `n, ` `int` `k)` `{` ` ` ` ` `// Boundaries of the Binary Search` ` ` `int` `l = ` `0` `, u = (` `int` `)1e9;` ` ` `while` `(l < u)` ` ` `{` ` ` ` ` `// Find the middle value` ` ` `int` `m = (l + u) / ` `2` `;` ` ` ` ` `// Check for the middle value` ` ` `if` `(check(a, b, k, m))` ` ` ` ` `// Update the upper` ` ` `u = m;` ` ` `else` ` ` ` ` `// Update the lower` ` ` `l = m + ` `1` `;` ` ` `}` ` ` `return` `l;` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `n = ` `5` `;` ` ` `int` `k = ` `12` `;` ` ` `int` `a[] = { ` `2` `, ` `1` `, ` `4` `, ` `3` `, ` `5` `};` ` ` `int` `b[] = { ` `4` `, ` `3` `, ` `2` `, ` `3` `, ` `1` `};` ` ` ` ` `System.out.println(findMin(a, b, n, k));` `}` `}` `// This code is contributed by ayush_dragneel` |

## Python3

`# Python 3 program for the above approach` `# Function to check if there exists an` `# X that satisfies the given conditions` `def` `check(a, b, k, n, x):` ` ` `sum` `=` `0` ` ` `# Find the required value of the` ` ` `# given expression` ` ` `for` `i ` `in` `range` `(n):` ` ` `sum` `=` `sum` `+` `pow` `(` `max` `(a[i] ` `-` `x, ` `0` `), b[i])` ` ` `if` `(` `sum` `<` `=` `k):` ` ` `return` `True` ` ` `else` `:` ` ` `return` `False` `# Function to find the minimum value` `# of X using binary search.` `def` `findMin(a, b, n, k):` ` ` `# Boundaries of the Binary Search` ` ` `l ` `=` `0` ` ` `u ` `=` `max` `(a)` ` ` `while` `(l < u):` ` ` `# Find the middle value` ` ` `m ` `=` `(l ` `+` `u) ` `/` `/` `2` ` ` `# Check for the middle value` ` ` `if` `(check(a, b, k, n, m)):` ` ` `# Update the upper` ` ` `u ` `=` `m` ` ` `else` `:` ` ` `# Update the lower` ` ` `l ` `=` `m ` `+` `1` ` ` `return` `l` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `arr ` `=` `[` `2` `, ` `1` `, ` `4` `, ` `3` `, ` `5` `]` ` ` `brr ` `=` `[` `4` `, ` `3` `, ` `2` `, ` `3` `, ` `1` `]` ` ` `K ` `=` `12` ` ` `N ` `=` `len` `(arr)` ` ` `print` `(findMin(arr, brr, N, K))` ` ` `# This code is contributed by ipg2016107.` |

## C#

`// C# program for the above approach` `using` `System;` `public` `class` `GFG{` ` ` `// Function to check if it is possible to` `// get desired result` `static` `bool` `check(` `int` `[]a, ` `int` `[]b, ` `int` `k, ` `int` `x)` `{` ` ` `int` `sum = 0;` ` ` `for` `(` `int` `i = 0; i < a.Length; i++)` ` ` `{` ` ` `sum = sum + (` `int` `)Math.Pow(` ` ` `Math.Max(a[i] - x, 0), b[i]);` ` ` `}` ` ` `if` `(sum <= k)` ` ` `return` `true` `;` ` ` `else` ` ` `return` `false` `;` `}` `// Function to find the minimum value` `// of X using binary search.` `static` `int` `findMin(` `int` `[]a, ` `int` `[]b, ` `int` `n, ` `int` `k)` `{` ` ` ` ` `// Boundaries of the Binary Search` ` ` `int` `l = 0, u = (` `int` `)1e9;` ` ` `while` `(l < u)` ` ` `{` ` ` ` ` `// Find the middle value` ` ` `int` `m = (l + u) / 2;` ` ` ` ` `// Check for the middle value` ` ` `if` `(check(a, b, k, m))` ` ` ` ` `// Update the upper` ` ` `u = m;` ` ` `else` ` ` ` ` `// Update the lower` ` ` `l = m + 1;` ` ` `}` ` ` `return` `l;` `}` `// Driver code` `public` `static` `void` `Main(String[] args)` `{` ` ` `int` `n = 5;` ` ` `int` `k = 12;` ` ` `int` `[]a = { 2, 1, 4, 3, 5 };` ` ` `int` `[]b = { 4, 3, 2, 3, 1 };` ` ` ` ` `Console.WriteLine(findMin(a, b, n, k));` `}` `}` `// This code is contributed by Princi Singh` |

## Javascript

`<script>` ` ` `// JavaScript program for the above approache9 + 7;` ` ` `// Function to check if there exists an` ` ` `// X that satisfies the given conditions` ` ` `function` `check(a, b, k, n, x) {` ` ` `let sum = 0;` ` ` `// Find the required value of the` ` ` `// given expression` ` ` `for` `(let i = 0; i < n; i++) {` ` ` `sum = sum + Math.pow(Math.max(a[i] - x, 0), b[i]);` ` ` `}` ` ` `if` `(sum <= k)` ` ` `return` `true` `;` ` ` `else` ` ` `return` `false` `;` ` ` `}` ` ` `function` `max_element(a) {` ` ` `let maxi = Number.MIN_VALUE;` ` ` `for` `(let i = 0; i < a.length; i++) {` ` ` `if` `(a[i] > maxi) {` ` ` `maxi = a[i];` ` ` `}` ` ` `}` ` ` `return` `maxi;` ` ` `}` ` ` `// Function to find the minimum value` ` ` `// of X using binary search.` ` ` `function` `findMin(a, b, n, k) {` ` ` `// Boundaries of the Binary Search` ` ` `let l = 0, u = max_element(a);` ` ` `while` `(l < u) {` ` ` `// Find the middle value` ` ` `let m = Math.floor((l + u) / 2);` ` ` `// Check for the middle value` ` ` `if` `(check(a, b, k, n, m)) {` ` ` `// Update the upper` ` ` `u = m;` ` ` `}` ` ` `else` `{` ` ` `// Update the lower` ` ` `l = m + 1;` ` ` `}` ` ` `}` ` ` `return` `l;` ` ` `}` ` ` `// Driver Code` ` ` `let arr = [2, 1, 4, 3, 5];` ` ` `let brr = [4, 3, 2, 3, 1];` ` ` `let K = 12;` ` ` `let N = arr.length;` ` ` `document.write(findMin(arr, brr, N, K));` `// This code is contributed by Potta Lokesh` ` ` `</script>` |

**Output**

2

**Time Complexity:** O(N*log M), where, M is the *maximum element of the array**.***Auxiliary Space:** O(1)

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**.