Given four integers a, b, c, and k. The task is to find the minimum positive value of x such that ax2 + bx + c ≥ k.
Examples:
Input: a = 3, b = 4, c = 5, k = 6
Output: 1
For x = 0, a * 0 + b * 0 + c = 5 < 6
For x = 1, a * 1 + b * 1 + c = 3 + 4 + 5 = 12 > 6Input: a = 2, b = 7, c = 6, k = 3
Output: 0
Brute Force Approach:
The brute force approach to solve this problem would be to iterate over all possible values of x starting from 0 and check if ax^2 + bx + c is greater than or equal to k. If the condition is satisfied for any value of x, we return that x as the minimum positive integer satisfying the given equation.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to return the minimum positive// integer satisfying the given equationint MinimumX(int a, int b, int c, int k){ int x = 0; while(a*x*x + b*x + c < k) { x++; } return x;}// Driver codeint main(){ int a = 3, b = 2, c = 4, k = 15; cout << MinimumX(a, b, c, k); return 0;} |
Java
import java.util.*;public class Main { // Function to return the minimum positive // integer satisfying the given equation public static int MinimumX(int a, int b, int c, int k) { int x = 0; while(a*x*x + b*x + c < k) { x++; } return x; } // Driver code public static void main(String[] args) { int a = 3, b = 2, c = 4, k = 15; System.out.println(MinimumX(a, b, c, k)); }} |
Python3
# Function to return the minimum positive# integer satisfying the given equationdef MinimumX(a, b, c, k): x = 0 while a*x*x + b*x + c < k: x += 1 return x# Driver codedef main(): a = 3 b = 2 c = 4 k = 15 print(MinimumX(a, b, c, k))if __name__ == "__main__": main() |
C#
using System;public class Program{ // Function to return the minimum positive // integer satisfying the given equation static int MinimumX(int a, int b, int c, int k) { int x = 0; while (a * x * x + b * x + c < k) { x++; } return x; } // Driver code public static void Main() { int a = 3, b = 2, c = 4, k = 15; Console.WriteLine(MinimumX(a, b, c, k)); }} |
Javascript
// Function to return the minimum positive// integer satisfying the given equationfunction MinimumX(a, b, c, k) { let x = 0; while (a * x * x + b * x + c < k) { x++; } return x;}// Driver code const a = 3, b = 2, c = 4, k = 15; console.log(MinimumX(a, b, c, k)); |
Output
2
Time Complexity: O(K)
Auxiliary Space: O(1)
Approach: The idea is to use binary search. The lower limit for our search will be 0 since x has to be minimum positive integer.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the minimum positive// integer satisfying the given equationint MinimumX(int a, int b, int c, int k){ int x = INT_MAX; if (k <= c) return 0; int h = k - c; int l = 0; // Binary search to find the value of x while (l <= h) { int m = (l + h) / 2; if ((a * m * m) + (b * m) > (k - c)) { x = min(x, m); h = m - 1; } else if ((a * m * m) + (b * m) < (k - c)) l = m + 1; else return m; } // Return the answer return x;}// Driver codeint main(){ int a = 3, b = 2, c = 4, k = 15; cout << MinimumX(a, b, c, k); return 0;} |
Java
// Java implementation of the approachclass GFG{ // Function to return the minimum positive// integer satisfying the given equationstatic int MinimumX(int a, int b, int c, int k){ int x = Integer.MAX_VALUE; if (k <= c) return 0; int h = k - c; int l = 0; // Binary search to find the value of x while (l <= h) { int m = (l + h) / 2; if ((a * m * m) + (b * m) > (k - c)) { x = Math.min(x, m); h = m - 1; } else if ((a * m * m) + (b * m) < (k - c)) l = m + 1; else return m; } // Return the answer return x;}// Driver codepublic static void main(String[] args){ int a = 3, b = 2, c = 4, k = 15; System.out.println(MinimumX(a, b, c, k));}}// This code is contributed by Code_Mech. |
Python3
# Python3 implementation of the approach# Function to return the minimum positive# integer satisfying the given equationdef MinimumX(a, b, c, k): x = 10**9 if (k <= c): return 0 h = k - c l = 0 # Binary search to find the value of x while (l <= h): m = (l + h) // 2 if ((a * m * m) + (b * m) > (k - c)): x = min(x, m) h = m - 1 elif ((a * m * m) + (b * m) < (k - c)): l = m + 1 else: return m # Return the answer return x# Driver codea, b, c, k = 3, 2, 4, 15print(MinimumX(a, b, c, k))# This code is contributed by mohit kumar |
C#
// C# implementation of the approachusing System;class GFG{ // Function to return the minimum positive// integer satisfying the given equationstatic int MinimumX(int a, int b, int c, int k){ int x = int.MaxValue; if (k <= c) return 0; int h = k - c; int l = 0; // Binary search to find the value of x while (l <= h) { int m = (l + h) / 2; if ((a * m * m) + (b * m) > (k - c)) { x = Math.Min(x, m); h = m - 1; } else if ((a * m * m) + (b * m) < (k - c)) l = m + 1; else return m; } // Return the answer return x;}// Driver codepublic static void Main(){ int a = 3, b = 2, c = 4, k = 15; Console.Write(MinimumX(a, b, c, k));}}// This code is contributed by Akanksha Rai |
Javascript
<script>// Javascript implementation of the approach// Function to return the minimum positive// integer satisfying the given equationfunction MinimumX(a,b,c,k){ let x = Number.MAX_VALUE; if (k <= c) return 0; let h = k - c; let l = 0; // Binary search to find the value of x while (l <= h) { let m = Math.floor((l + h) / 2); if ((a * m * m) + (b * m) > (k - c)) { x = Math.min(x, m); h = m - 1; } else if ((a * m * m) + (b * m) < (k - c)) l = m + 1; else return m; } // Return the answer return x;}// Driver codelet a = 3, b = 2, c = 4, k = 15;document.write(MinimumX(a, b, c, k));// This code is contributed by patel2127</script> |
PHP
<?php// PHP implementation of the approach // Function to return the minimum positive // integer satisfying the given equation function MinimumX($a, $b, $c, $k) { $x = PHP_INT_MAX; if ($k <= $c) return 0; $h = $k - $c; $l = 0; // Binary search to find the value of x while ($l <= $h) { $m = floor(($l + $h) / 2); if (($a * $m * $m) + ($b * $m) > ($k - $c)) { $x = min($x, $m); $h = $m - 1; } else if (($a * $m * $m) + ($b * $m) < ($k - $c)) $l = $m + 1; else return $m; } // Return the answer return $x; } // Driver code $a = 3; $b = 2; $c = 4; $k = 15; echo MinimumX($a, $b, $c, $k);// This code is contributed by Ryuga?> |
Output
2
Time Complexity : O(log(k-c))
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!
