Найдите минимальное положительное целое число x такое, что a (x ^ 2) + b (x) + c> = k

Опубликовано: 14 Января, 2022

Даны четыре целых числа 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 > 6

Input: 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
?>
Output:
2

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ