Найдите минимальное положительное целое число x такое, что a (x ^ 2) + b (x) + c> = k
Даны четыре целых числа a , b , c и k . Задача состоит в том, чтобы найти минимальное положительное значение x такое, что ax 2 + bx + c ≥ k .
Примеры:
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
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: идея заключается в использовании бинарного поиска. Нижний предел для нашего поиска будет 0, так как x должно быть минимальным положительным целым числом.
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 equation int 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 code int main() { int a = 3, b = 2, c = 4, k = 15; cout << MinimumX(a, b, c, k); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the minimum positive // integer satisfying the given equation static 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 code public 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 equation def 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 code a, b, c, k = 3 , 2 , 4 , 15 print (MinimumX(a, b, c, k)) # This code is contributed by mohit kumar |
C#
// C# implementation of the approach using System; class GFG { // Function to return the minimum positive // integer satisfying the given equation static 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 code public 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 |
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 ?> |
2
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.