Матч 7, Пять в ряд (StraightArray)

Массив чисел содержит стрит, если в нем существуют пять последовательных целых чисел. Например, массив {6, 1, 9, 5, 7, 15, 8} содержит стрит, так как в нем есть числа 5, 6, 7, 8 и 9. Необходимо добавить к массиву nums наименьшее количество чисел так, чтобы он содержал стрит.

Класс: StraightArray

Метод: int howManyMore(vector<int> nums)

Ограничения: text содержит от 1 до 50 символов ‘a’ – ‘z’, ‘A’ – ‘Z’, ‘0’ – ‘9’, ‘ ‘ (пробел).

Вход. Массив чисел nums.

Выход. Наименьшее количество чисел, которое следует добавить в массив nums, чтобы он содержал стрит.

Пример входа

nums

{5, 6, 7}

{5, 7, 9, 8492, 8493, 192398}

{6, 1, 9, 5, 7, 15, 8}

Пример выхода

2

2

0

РЕШЕНИЕ

полный перебор

Для каждого числа i массива nums в переменной s подсчитываем, сколько чисел из множества {i, i + 1, i + 2, i + 3, i + 4} содержится в массиве. В переменной res запоминаем наибольшее из подсчитанных значений. Возвращаем ответ на задачу, равный 5 – res.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

class StraightArray

{

public:

int howManyMore(vector<int> nums)

{

int i, j, s, res;

vector<int>::iterator iter;

for(res = i = 0; i < (int)nums.size(); i++)

{

for(s = j = 1; j < 5; j++)

{

iter = find(nums.begin(),nums.end(),nums[i] + j);

if (iter != nums.end()) s++;

}

if (s > res) res = s;

}

return 5 - res;

}

};