Найдите недостающие числа как это

16 15 17 14 32 33 31 34 вставьте недостающие числа

Загадки на логику

Похожие новости

Приветствую вас, дорогие читатели!

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

Надеюсь, вы быстро найдете решение.

Ответы оставляйте в комментариях.

Головоломка первая

Головоломка вторая

Понравились задания? Тогда не забудьте поставить статье лайк и подписаться на канал

Удачи!

Учитывая массив n-1 различные целые числа в диапазоне от 1 до n, найти в нем пропущенное число за линейное время.

Например, рассмотрим массив {1, 2, 3, 4, 5, 7, 8, 9, 10} элементы которого различны и находятся в диапазоне от 1 до 10. Недостающее число — 6.

Потренируйтесь в этой проблеме

1. Использование формулы для суммы первых n Натуральные числа

Мы знаем, что сумма первых n натуральные числа можно вычислить по формуле 1 + 2 + … + n = n×(n+1)/2. Мы можем использовать эту формулу, чтобы найти пропущенное число.

Идея состоит в том, чтобы найти сумму целых чисел от 1 до n+1 используя приведенную выше формулу, где n размер массива. Также вычислите фактическую сумму целых чисел в массиве. Теперь недостающее число будет разницей между ними.

Этот подход демонстрируется ниже на C, Java и Python:

2. Использование оператора XOR

Мы знаем, что XOR двух одинаковых чисел отменяет друг друга. Мы можем воспользоваться этим фактом, чтобы найти недостающее число в массиве с ограниченным диапазоном.

Идея состоит в том, чтобы вычислить XOR всех элементов массива и вычислить XOR всех элементов от 1 до n+1, куда n размер массива. Теперь недостающее число будет XOR между ними.

Этот подход демонстрируется ниже на C, Java и Python:

Временная сложность обоих рассмотренных выше методов составляет O(n) и не требует дополнительного места, где n это размер ввода.

Один из наиболее часто задаваемых вопросов на собеседованиях — найти пропущенное число в массиве на Java, C # или любом другом языке. Такого рода вопросы задаются не только в небольших стартапах, но и в некоторых крупнейших технических компаниях, таких как Google, Amazon, Facebook, Microsoft.

В простейшей версии этого вопроса надо найти недостающий элемент в массиве целых чисел, содержащем числа от 1 до 100. Это можно легко решить, вычислив предполагаемую сумму с помощью n (n + 1) /2 и отняв от нее сумму всех существующих элементов массива. Это также один из самых быстрых и эффективных способов, но его нельзя использовать, если массив содержит более одного пропущенного числа или если массив содержит дубликаты.

Это дает интервьюеру несколько хороших намеков, чтобы проверить, может ли кандидат применить свои знания в несколько иных состояниях или нет. Поэтому, если вы справитесь с первым подходом, вас попросят найти пропущенное число в массиве с дубликатами или с несколькими пропущенными числами. Это может быть более сложно, но вы скоро обнаружите, что другой способ найти пропущенное и повторяющееся число в массиве — это отсортировать его.

В отсортированном массиве вы можете сравнить, равно ли число ожидаемому следующему числу или нет.

Кроме того, вы также можете использовать BitSet в Java для решения этой проблемы — надо перебрать все записи и использовать набор битов, чтобы запомнить, какие числа установлены, а затем проверить на 0 бит. Запись с битом 0 является отсутствующим номером.

Найти пропущенное число в массиве: решение на Java

import java.util.Arrays;
import java.util.BitSet;
 
public class MissingNumberInArray {
 
    public static void main(String args[]) {

        // one missing number
        printMissingNumber(new int[]{1, 2, 3, 4, 6}, 6);
 
        // two missing number
        printMissingNumber(new int[]{1, 2, 3, 4, 6, 7, 9, 8, 10}, 10);
 
        // three missing number
        printMissingNumber(new int[]{1, 2, 3, 4, 6, 9, 8}, 10);
 
        // four missing number
        printMissingNumber(new int[]{1, 2, 3, 4, 9, 8}, 10);
 
        // Only one missing number in array
        int[] iArray = new int[]{1, 2, 3, 5};
        int missing = getMissingNumber(iArray, 5);
        System.out.printf("Missing number in array %s is %d %n",

                           Arrays.toString(iArray), missing);
    }

   /**
    * A general method to find missing values from an integer array in Java.
    * This method will work even if array has more than one missing element.
    */
    private static void printMissingNumber(int[] numbers, int count) {
        int missingCount = count - numbers.length;
        BitSet bitSet = new BitSet(count);
 
        for (int number : numbers) {
            bitSet.set(number - 1);
        }
 
        System.out.printf("Missing numbers in integer array %s, with total number %d is %n",
        Arrays.toString(numbers), count);
        int lastMissingIndex = 0;

        for (int i = 0; i < missingCount; i++) {
            lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);
            System.out.println(++lastMissingIndex);
        }
 
    }

   /**
    * Java method to find missing number in array of size n containing

    * numbers from 1 to n only.
    * can be used to find missing elements on integer array of

    * numbers from 1 to 100 or 1 - 1000
    */
    private static int getMissingNumber(int[] numbers, int totalCount) {
        int expectedSum = totalCount * ((totalCount + 1) / 2);
        int actualSum = 0;
        for (int i : numbers) {
            actualSum += i;
        }
 
        return expectedSum - actualSum;
    }
 
}

Алгоритм с XOR

Мы можем использовать свойство XOR, чтобы получить решение этой проблемы, не беспокоясь о проблеме переполнения битов. Кроме того, XOR безопаснее и быстрее суммирования. Мы знаем свойство XOR, что XOR двух одинаковых чисел равен 0 ( A XOR A = 0). Если мы вычислим XOR всех чисел от 1 до N (это включает в себя неизвестное пропущенное число), а затем с этим результатом, XOR всех заданных чисел, общие числа будут отменены (так как A XOR A=0), и в конце мы получим пропущенное число. Если у нас нет проблемы переполнения битов, мы можем использовать как суммирование, так и алгоритмы на основе XOR, чтобы получить решение. Но алгоритм, использующий XOR, безопаснее и быстрее, чем алгоритм, который использует суммирование, вычитание и умножение. И мы можем избежать дополнительных забот, вызванных суммированием, вычитанием и умножением.

long n = 100;
long a[] = new long[n];

//XOR of all numbers from 1 to n
// n%4 == 0 ---> n
// n%4 == 1 ---> 1
// n%4 == 2 ---> n + 1
// n%4 == 3 ---> 0

//Slower way of implementing the formula
// long xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0;
//Faster way of implementing the formula
// long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);

long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);

for (long i = 0; i < n; i++)
{
   xor = xor ^ a[i];
}
//Missing number
System.out.println(xor);

Если вы нашли опечатку – выделите ее и нажмите Ctrl + Enter! Для связи с нами вы можете использовать info@apptractor.ru.

Ввод: nums = [3,0,1]
Вывод: 2
Пояснение: n = 3, так как всего элементов в массиве три, поэтому все элементы 
находятся в диапазоне [0,3]. 2 — недостающий элемент.

Ввод: nums = [0,1]
Вывод: 2
Пояснение: n = 2, так как всего элементов в массиве два, поэтому все элементы 
находятся в диапазоне [0,2]. 2 — недостающий элемент.

Ввод: nums = [9,6,4,2,3,5,7,0,1]
Вывод: 8
Пояснение: n = 9, так как всего элементов в массиве девять, поэтому все элементы 
находятся в диапазоне [0,9]. 8 — недостающий элемент.

public int missingNumber(int[] nums) {
    int realSum = 0;
    int sum = 0;

    for (int num : nums) {
        sum += num;
    }

    for (int i = 0; i <= nums.length; i++) {
        realSum += i;
    }
    return realSum - sum;
}

public int missingNumber(int[] nums) {
    int rez = 0;
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += (i + 1);
        rez += nums[i];
    }
    return sum - rez;
}

Научитесь: Профессия Java-разработчик
Узнать больше