Как проверить, содержит ли массив пару чисел, произведение которых нечетно?

Question

Как я могу написать функцию, которая принимает массив целых чисел и возвращает true, если существует пара чисел, произведение которых нечетно?

Каковы свойства нечетных целых чисел? И, конечно же, как вы пишете эту функцию на Java? Также, возможно, краткое объяснение того, как вы пошли о разработке алгоритма для фактической реализации.

Да, это функция из учебника. Нет, это не домашняя работа - я просто пытаюсь учиться, поэтому, пожалуйста, не "делайте свои домашние комментарии".

Answer 1

Нечетное число не делится поровну на два. Все, что вам нужно знать, это два нечетных числа в наборе. Просто проверьте, не является ли каждое число мод 2 ненулевым. Если так, то это странно. Если вы найдете два нечетных числа, вы можете умножить их и получить еще одно нечетное число.

Примечание: нечетное число, умноженное на четное число, всегда является четным.

Answer 2

Произведение двух целых будет нечетным только , если оба целых нечетны. Итак, чтобы решить эту проблему, просто просканируйте массив один раз и посмотрите, есть ли два (или более) нечетных целых числа.

РЕДАКТИРОВАТЬ: Как уже упоминалось, вы проверяете, не является ли число нечетным, используя оператор модуля (%). Если N% 2 == 0, то число четное.

Answer 3

Свойства, о которых стоит задуматься:

• Нечетные числа не делятся на 2
• Любое число, умноженное на четное число, является четным

Таким образом, вы можете переформулировать вопрос как:

Содержит ли массив хотя бы два целых числа, которые не делятся на 2?

Что должно облегчить жизнь.

Answer 4

Спасибо за ваши ответы и комментарии.

Теперь я хорошо понимаю, как проверить, является ли целое число нечетным. Например, этот метод представляет собой удобный способ выполнить этот тест без использования операторов умножения, модуля или деления:

 protected boolean isOdd(int i) {
    return ( (i&1) == 1);

}

С вашей помощью я теперь понимаю, что проблема намного проще, чем я ожидал. Вот остальная часть моей реализации в Java. Комментарии и критика приветствуются.

protected boolean isOddProduct(int[] arr) {
        int oddCount = 0;
        if (arr.length < 2) 
            throw new IllegalArgumentException();
        for (int i = 0; i <= arr.length-1; i++) {
            if (isOdd(arr[i]))
                oddCount++; 
        }
        return oddCount > 1;
    }

Интересно, существуют ли другие способы выполнить этот тест без использования *,% или / операторов? Может быть, я задам этот вопрос в новой теме.

Answer 5

Алгоритм перебора:

public static boolean hasAtLeastTwoOdds(int[] args) {
    int[] target = args; // make defensive copy
    int oddsFound;
    int numberOddsSought = 2;

    for (int i = 0; i < target.length; i++) {
        if (target[i] % 2 != 0) {
            if (oddsFound== numberOddsSought) {
                return true;
            }
            oddsFound++;
        }
    }

    return false;
}

Answer 6

Вы можете проверить на четность (или нечетность), используя модуль.

i% 2 = 0, если я четный; проверить это, и вы можете узнать, является ли число четным / нечетным