Проблема :
Вам дадут два массива целых чисел и попросят определить все целые числа, которые удовлетворяют следующим двум условиям:
- Элементами первого массива являются все множители рассматриваемого целого числа.
- Рассматриваемое целое число является множителем всех элементов второго массива
Эти числа называются между двумя массивами. Вы должны определить, сколько существует таких чисел.
Например, если заданы массивы a =[2, 6]
и b = [24, 36]
, между ними есть два числа: 6
и 12
. 6 % 2 = 0
, 6 % 6 = 0
, 24 % 6 = 0
и 36 % 6 = 0
для первого значения. Точно так же 12 % 2 = 0
, 12 % 6 = 0
и 24 % 12 = 0
, 36 % 12 = 0
.
Полностью задачу читайте здесь: Между двумя сетами
Решение :
Сначала мы сортируем оба массива в порядке возрастания, потому что значения можно вводить в любом порядке. Пусть первый массив равен factors
, а второй массив равен multiples
(см. условия 1 и 2).
std::sort(factors.begin(), factors.end());
std::sort(multiples.begin(), multiples.end());
Рассматриваемый диапазон целых чисел — от последнего элемента множителей до первого элемента кратных. Пусть это целое число равно num
. Итак, num = { factors.back(), ... , multiplies.front() }
.
unsigned short num = factors.back();
unsigned short times_multiplied = 2;
Здесь num
также содержат целые числа, не кратные 2
и 6
, например. 7, 11, 13, 15 ...
Чтобы сделать программу эффективной, num
должно содержать кратное factors.back()
i. е. в приведенном выше примере кратно 6. Таким образом, num = {6, 12, 18, 24 }
и числа, которые удовлетворяют двум вышеуказанным условиям, равны 6 and 12
.
num = factors.back() * times_multiplied;
times_multiplied++;
Логическая переменная is_multiple
сообщает, является ли число кратным num
, а is_factor
сообщает, является ли num
множителем числа.
bool is_multiple = true;
bool is_factor = true;
Если is_multiple
равно true
для всех элементов factors
, а is_factor
равно true
для всех элементов multiplies
для num
, то num
принадлежит между двумя массивами, и наша переменная count
увеличивается на 1.
for (unsigned int i = 0; i < factors.size(); ++i)
{
if (num % factors[i] != 0)
{
is_multiple = false;
break;
}
}
for (unsigned int j = 0; j < multiples.size(); ++j)
{
if (is_multiple && multiples[j] % num != 0)
{
is_factor = false;
break;
}
}
if (is_multiple && is_factor)
{
count++;
}
Для реализации C++ посетите Programmercave
Вам также может понравиться
Kangaroo HackerRank Challenge
Roy and Code Streak HackerEarth Challenge
Первоначально опубликовано на https://programmercave0.github.io 29 ноября 2019 г.