Минимизируйте значение |A – X| + |Б – У| + |С – Z| такое, что X * Y = Z

Даны три целых числа A , B и C , задача состоит в том, чтобы найти минимально возможное значение |A – X| + |Б – У| + |С – Z| такой, что X * Y = Z .

Пример :

Input: A = 19, B = 28, C = 522
Output: 2
Explanation: The most optimal choice of X, Y, and Z for the given A, B, and C are X = 18, Y = 29, and Z = 522. The equation X * Y = Z holds true and the value of |A – X| + |B – Y| + |C – Z| = 2 which is minimum possible.

Input: A = 11, B = 11, C = 121
Output: 0
Explanation: The given values of A, B, and C satisfies A * B = C. Therefore the most optimal choice is X = A, Y = B, and Z = C.

Подход: Вышеупомянутая проблема может быть решена с использованием следующих наблюдений:

• Максимальное значение |A – X| + |Б – У| + |С – Z| может быть A + B + C для X , Y и Z равных 0 .
• Основываясь на приведенном выше наблюдении, перебор всех значений i * j , таких что i * j <= 2 * C , и выбор наилучшего значения является оптимальным выбором.

Следовательно, перебирайте все значения i в диапазоне [1, 2*C] и для каждого i перебирайте все значения j , такие что i * j <= 2 * C , и отслеживайте минимально возможное значение | А – я | + |В – j| + |С – я * j| .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(C*log C)
Вспомогательное пространство: O(1)