Минимизируйте разницу между любым кратным заданным трем числам с K

Опубликовано: 21 Сентября, 2022

Даны 4 целых числа A , B , C и K , задача состоит в том, чтобы найти минимальную разницу между любым кратным A, B и C с K

Примеры:

Input: A = 5, B =  4, C =  8, K = 9
output: 1
Explanation: Closest multiple of A, B and C greater than 9 is 10. Therefore, minimum difference is 10-9 = 1

Input: A = 6, B = 10, C = 9, K = 2
Output: 4
Explanation: Closest multiple of A, B and C greater than 2 is 6. Therefore, minimum difference is 6-2 = 4

Наивный подход . Задача может быть решена с помощью цикла for для получения следующих кратных A, B и C, путем отслеживания ближайшего кратного , чуть большего K. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте 3 логические переменные, скажем, fa, fb и fc, чтобы указать, становится ли кратное A, B и C больше, чем K
  • Начните умножать A, B и C с помощью cur , инициализированного 1
  • Как только одно из трех чисел станет больше K , сохраните разницу между ближайшим кратным и K соответственно

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


Временная сложность : O(мин(K/A, K/B, K/C))
Вспомогательное пространство : O(1)

Эффективный подход : описанный выше подход может быть обобщен формулой: min(⌈K/A⌉*A, ⌈K/B⌉*B, ⌈K/C⌉*C) − K .

  • ⌈K/A⌉*A дает ближайшее кратное A , чуть большее, чем K
  • ⌈K/B⌉*B дает ближайшее кратное B , чуть большее, чем K
  • ⌈K/C⌉*C дает ближайшее кратное C , чуть большее, чем K
  • Разница минимума всего этого с K дает желаемый результат

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


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

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