Проблема :

Вам дадут два массива целых чисел и попросят определить все целые числа, которые удовлетворяют следующим двум условиям:

  1. Элементами первого массива являются все множители рассматриваемого целого числа.
  2. Рассматриваемое целое число является множителем всех элементов второго массива

Эти числа называются между двумя массивами. Вы должны определить, сколько существует таких чисел.

Например, если заданы массивы 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 г.