Выдающаяся чётность

15 Август 2019 - Время чтения: 16 минуты

Условие задачи: Дан массив целых чисел. Все числа, кроме одного, имеют одну и ту же чётность. Например, только одно число чётное, а все остальные нечётные. Или наоборот. Определить, какое число встречается один раз, чётное или нечётное. Минимальная длина массива - 3 элемента. Массив может быть очень большим, поэтому желательно найти решение, которое не потребует анализа все элементов.

Давайте подумаем. Первое, что приходит в голову - завести две переменные, количество чётных и количество нечётных. Подсчитать те и другие, и какое из них только в одном экземпляре, то и является ответом. Решение простое и бесхитростное. Давайте реализуем его, хотя бы просто для контраста с другими решениями. Только я предлагаю не заводить две переменные, а завести массив из двух элементов, так удобнее.


Исходный код на C99
#include <stdio.h>
 
int main(void)
{
    int a[] = {0, 0};
    for (int x; scanf("%d", &x) == 1;) {
        ++a[x & 1];
    }
    printf("%s\n", a[0] == 1 ? "Even" : "Odd");
    return 0;
}

Можно заметить, что одних чисел гарантированно больше, чем других. Например, если чётное одно, то нечётных как минимум два. Поэтому достаточно завести одну переменную, которая будет хранить баланс чисел. Мы будем либо увеличивать, либо уменьшать баланс, в зависимости от чётности числа. А потом посмотрим, какой получился баланс, положительный или отрицательный. Нулю он никак не может быть равен. Более того, при желании можно проверять дополнительно, не стал ли он больше единицы по модулю. Потому что дальше он будет идти в ту же сторону.


Исходный код на C99
#include <stdio.h>
 
int main(void)
{
    int b = 0;
    for (int x; scanf("%d", &x) == 1;) {
        b += x & 1 ? -1 : 1;
    }
    printf("%s\n", b < 0 ? "Even" : "Odd");
    return 0;
}

Однако хотелось бы, конечно, более эффективное решение. Интуитивно ясно, что оно есть, ведь если какая-то разновидность чисел встретилась хотя бы пару раз, то уже понятно, что ответом является другая разновидность.

Я предлагаю рассмотреть все возможные варианты начала последовательностей чисел. Обозначим чётные и нечётные, соответственно, буквами Ч и Н.

  1. Ч, Ч... Уже понятно, что чётных больше одного, а значит ответом является Н.
  2. Ч, Н, Ч...
  3. Ч, Н, Н... Если два первых числа разных типов, то уж по третьему можно судить точно.
  4. Н, Н... Ну и дальше те же самые варианты, только наоборот.

Таким образом, есть всего 6 вариантов, и для того, чтобы решить задачу, достаточно прочитать три первых числа. Если чётных среди них больше одного, значит ответом является нечётное, и наоборот. Реализуем этот принцип.


Исходный код C#
using System;
using System.Linq;
 
class Program
{
    public static void Main()
    {
        int[] a = Console.ReadLine().Split().Select(Int32.Parse).ToArray();
        Console.WriteLine(a.Take(3).Count(x => x % 2 == 0) > 1 ? "Odd" : "Even");
    }
}

Видно, что мы анализируем первые три элемента массива, но мы только что выяснили, что в некоторых случаях достаточно даже двух элементов. Можно ли ещё оптимизировать алгоритм? Учитывая, что возможных ситуаций не так много, можно построить машину состояний.

Состояния:

  1. Начальное состояние. Если прочитано Ч, переходим в состояние 1, иначе в 2.
  2. Ранее прочитано Ч. Если сейчас прочитано ещё одно - ответ получен, и это Н. Обозначим это состояние -1. Если прочитано Н - переходим в состояние 3.
  3. Ранее прочитано Н. Если сейчас прочитано ещё одно - ответ Ч, обозначим это состояние -2. Если нет - переходим в состояние 3, потому что Н, Ч эквивалентно Ч, Н, в обоих случаях решение принимается по третьему члену.
  4. Ранее прочитаны Ч, Н или Н, Ч. Если сейчас прочитано Ч, переходим в состояние -1, иначе -2.

Таким образом, если после завершения цикла мы в состоянии -1, то ответ Н, иначе Ч.


Исходный код Python
state = 0
 
for x in map(int, input().split()):
    even = x % 2 == 0
    if state == 0:
        state = 1 if even else 2
    elif state == 1:
        state = -1 if even else 3
    elif state == 2:
        state = 3 if even else -2
    else:
        state = -1 if even else -2
    if state < 0:
        break
 
print("Odd" if state == -1 else "Even")

Машина состояний - очень удобный и простой инструмент. Многие программы, от компиляторов языков программирования до компьютерных игр, зачастую реализуются как машины состояний. Разумеется, гораздо более сложные. Возможно, я расскажу об этом в одной из следующих статей. Интересно ли это Вам?

Байт
Written by Байт on 4 Ноябрь 2019
Напомнило мне одну любопытную задачку Есть массив целочисленных неотрицательных значений размером, ну скажем, 1000000001 элемент, заполненный одним одним миллиардом парных (парное число встречается в массиве 2 раза) и одним непарным числом. Задача: найти это единственное непарное число. Это не твой метод сотояний. Но нашедший решение - да возрадуется!

Коротко обо мне

Меня зовут Вадим Тукаев, я репетитор по информатике и программированию. Вы можете сконтактировать со мной по почте vadimtukaev@gmail.com или по скайпу pol6energetik. Рассмотрю и другие предложения о сотрудничестве, включая, но не ограничиваясь, написание заказного ПО для Windows/Linux.

Категории