Как правильно найти недостающее число - Сайт, где вы сможете решить свои вопросы

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

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

Желаю удачи в решении!

Задание первое

Задание второе

Какие ответы у вас получились?

Делитесь результатами в комментариях.

Не забудьте подписаться на мой канал, где вас ждет много других задач)

Благодарю за внимание!

Источник

#статьи

20 дек 2022
0

Задача: найти недостающий элемент массива

Решаем задачи, которые дают программистам на собеседованиях в IT‑компаниях. Сегодня ищем, какого элемента не хватает в массиве.

Иллюстрация: Polina Vari для Skillbox Media

Любитель научной фантастики и технологического прогресса. Хорошо сочетает в себе заумного технаря и утончённого гуманитария. Пишет про IT и радуется этому.

Условие. Дан массив целых чисел nums, в котором должны содержаться все числа из диапазона [0, n]. При этом n равно числу элементов в массиве, а значит, одного элемента всегда будет не хватать. Необходимо написать функцию, которая возвращает недостающее число из этого диапазона.


Ввод: 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 — недостающий элемент.

Решить эту задачу самостоятельно и на разных языках программирования можно на LeetCode. Наше решение взято из телеграм-канала Сергея Cracking code interview.

Решение

Нам нужно найти недостающее число. Из условия задачи мы знаем, что все элементы уникальные, то есть не повторяются. Поэтому если у нас есть, например, массив с размером в три элемента, то его элементы должны быть такими: [0, 1, 2, 3]. Однако размер у него 3, а значит, один из элементов всегда будет пропущен и массив будет выглядеть примерно так: [1, 0, 3].

Все элементы нашего массива всегда статичны, а значит, мы можем посчитать «идеальную» сумму всех элементов (в нашем случае от 1 до 3) и вычесть из неё сумму имеющихся в массиве чисел. Так мы найдём недостающее число:


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;
}

Это решение можно немного оптимизировать и задействовать всего один цикл for:


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;
}

Результаты

Временная сложность: O(n) — так как мы проходимся по всему массиву.

Ёмкостная сложность: O(1) — нам нужно заранее определённое количество места в памяти.

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

Источник

Алгоритм
нахождения пропущенного числа в начальной школе.

Мой педагогический
стаж 35 лет. Из них 34 года я проработала учителем начальных классов.
Педагогический опыт достаточно большой. За время работы мною найдены такие
приёмы организации учебной деятельности, благодаря которым основные понятия
программного материала как по русскому языку, так и по математике легко
воспринимаются и усваиваются учащимися с различным уровнем обученности.

Совсем недавно
я стала работать методистом по практике в Костанайском педагогическом
колледже. Достаточно часто во время подготовки и проведении зачётных уроков,
я сталкиваюсь с тем, что студенты нацеливают свою работу только на то, чтобы
выполнить задание – решить задачу, уравнение, найти значение выражения;
просклонять имя существительное, разобрать слово по составу и т. д. Но не
понимают, что очень важно научить детей анализировать задание и найти способ
его выполнения. А как это важно!

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

Итак,
достаточно часто в учебники по математике включают задания со звёздочкой вида:

… – 5 = 4,
… + 4 = 9, 9 – … = 6.

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

ð От какого числа
нужно отнять 5, чтобы получилось 4?

ð Ребята вспоминают
состав числа 9. 9 – это 5 и 4.

ð От 9 отнимаем 5,
остаётся 4.

ð Значит пропущенное
число – 4.

ð И так далее.

Но вот задания
усложняются и появляются задания вида:

10 – … +
3= 4

или

10 – …
+ 3 + 4 = 8

и ещё сложнее

10 – …
+ 3 + 4 – 6 +5 = 7

Как быть ученику?
Подбирать до бесконечности, пока не подойдёт одно из чисел?

Задумываясь над
подобным заданием, для себя я установила некую связь между предыдущими и
последующим действиями.

Я предлагаю
вникнуть в процесс анализа следующего выражения: 10 – … + 3= 4.
Начнем с последнего действия.

10 – … + 3 = 4

То, что закрашено
красным цветом, закрываем и представляем как один компонент – неизвестное число
(неизвестный компонент -слагаемое). Задаём детям вопрос: к какому числу
(слагаемому) нужно +3, чтобы стало 4? Конечно же к 1 (выделим жёлтым цветом).
Значит в той части, которая закрашена красным цветом (10-…) должно в результате
получится 1.

10-…=1 Нужно от
10 отнять 9, чтобы получилось число 1. Вот и пришли к искомому числу.

Проверим – 10
– 9 + 3= 4. Всё верно.

Рассмотрим
более сложное выражение: 10 – … + 3 + 4 – 6 +5 = 7

Анализ и
рассуждение начнём снова с конца.

10 – … + 3 + 4 – 6 + 5 = 7

Снова закрываем
всю запись до последнего действия. Рассуждаем так: к какому числу нужно
прибавить 5, чтобы получилось 7? Отвечаем: к 2.

Надписываем над
предпоследним действием число 2.

10 – … + 3 + 4 – 6 + 5 = 7

Продвигаемся в
своём рассуждении дальше.

10 – … + 3 + 4 – 6 + 5 = 7

Что закрашено
красным цветом- неизвестное число (или неизвестное уменьшаемое). От какого
числа нужно отнять 6, чтобы получилось 2? От 8. Надписываем над предпоследним действием.

8 2

10 – … + 3 + 4 – 6 + 5 = 7

Рассуждаем дальше.

К какому числу
(слагаемому) нужно прибавить 4, чтобы получилось 8? К 4.

Надписываем над
предпоследним действием 4. (выделено жёлтым цветом)

4 8

10 – … + 3 + 4

Идём дальше. К
какому числу нужно прибавить 3, чтобы в ответе получилось 4? К 1. Значит над
первым действием надписываем число 1 (выделено жёлтым цветом).

1 4

10 – … + 3

Вот и завершающий
этап. Сколько нужно отнять от 10, чтобы получить 1? Конечно же 9. Вставляем в
пустую клетку число 9.

10 – 9

И проверяем всё
выражение.

1
4 8 2 7

10 – 9 + 3
+ 4 – 6 + 5 = 7

Пропущенное число найдено. Так можно вести
рассуждение с любыми числами – от однозначного до многозначных. Попробуйте.
Действует.

1123095 – … + 347820 – 56208 + 3456=
935501

У меня получился ответ: 182662

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

Источник

Учитывая массив 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:

C

#include <stdio.h>

// Находим пропущенное число в заданном массиве

int getMissingNumber(int arr[], int n)

{

// фактический размер `n+1`, так как в массиве отсутствует число

int m = n + 1;

// получить сумму целых чисел от 1 до `n+1`

int total = m*(m + 1)/2;

// получаем реальную сумму целых чисел в массиве

int sum = 0;

for (int i = 0; i < n; i++) {

sum += arr[i];

}

// недостающее число – это разница между ожидаемой суммой

// и фактическая сумма

return total – sum;

}

int main()

{

int arr[] = { 1, 2, 3, 4, 5, 7, 8, 9, 10 };

int n = sizeof(arr)/sizeof(arr[0]);

printf(“The missing number is %d”, getMissingNumber(arr, n));

return 0;

}

Скачать Выполнить код

результат:

The missing number is 6

Java

import java.util.Arrays;

class Main

{

// Находим пропущенное число в заданном массиве

public static int getMissingNumber(int[] arr)

{

// получаем длину массива

int n = arr.length;

// фактический размер `n+1`, так как в массиве отсутствует число

int m = n + 1;

// получить сумму целых чисел от 1 до `n+1`

int total = m * (m + 1) / 2;

// получаем реальную сумму целых чисел в массиве

int sum = Arrays.stream(arr).sum();

// недостающее число – это разница между ожидаемой суммой

// и фактическая сумма

return total – sum;

}

public static void main(String[] args)

{

int[] arr = { 1, 2, 3, 4, 5, 7, 8, 9, 10 };

System.out.println(“The missing number is “ + getMissingNumber(arr));

}

Скачать Выполнить код

результат:

The missing number is 6

Python

# Найти недостающее число в заданном списке

def getMissingNumber(arr):

# получить длину массива

n = len(arr)

# Фактический размер # равен `n+1`, так как в списке отсутствует номер.

m = n + 1

# получить сумму целых чисел от 1 до `n+1`

total = m * (m + 1) // 2

# пропущенное число – это разница между ожидаемой суммой и

# фактическая сумма целых чисел в списке

return total – sum(arr)

if __name__ == ‘__main__’:

arr = [1, 2, 3, 4, 5, 7, 8, 9, 10]

print(‘The missing number is’, getMissingNumber(arr))

Скачать Выполнить код

результат:

The missing number is 6

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

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

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

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

C

#include <stdio.h>

// Находим пропущенное число в заданном массиве

int getMissingNumber(int arr[], int n)

{

// Вычислить XOR всех элементов массива

int xor = 0;

for (int i = 0; i < n; i++) {

xor = xor ^ arr[i];

}

// Вычислить XOR всех элементов от 1 до `n+1`

for (int i = 1; i <= n + 1; i++) {

xor = xor ^ i;

}

return xor;

}

int main()

{

int arr[] = { 1, 2, 3, 4, 5, 7, 8, 9, 10 };

int n = sizeof(arr) / sizeof(arr[0]);

printf(“The missing number is %d”, getMissingNumber(arr, n));

return 0;

}

Скачать Выполнить код

результат:

The missing number is 6

Java

class Main

{

// Находим пропущенное число в заданном массиве

public static int getMissingNumber(int[] arr)

{

// Вычислить XOR всех элементов массива

int xor = 0;

for (int i: arr) {

xor = xor ^ i;

}

// Вычислить XOR всех элементов от 1 до `n+1`

for (int i = 1; i <= arr.length + 1; i++) {

xor = xor ^ i;

}

return xor;

}

public static void main(String[] args)

{

int[] arr = { 1, 2, 3, 4, 5, 7, 8, 9, 10 };

System.out.println(“The missing number is “ + getMissingNumber(arr));

}

Скачать Выполнить код

результат:

The missing number is 6

Python

# Найти недостающее число в заданном списке

def getMissingNumber(arr):

# Вычислить XOR всех элементов в списке

xor = 0

for i in arr:

xor = xor ^ i

# Вычислить XOR всех элементов от 1 до `n+1`

for i in range(1, len(arr) + 2):

xor = xor ^ i

return xor

if __name__ == ‘__main__’:

arr = [1, 2, 3, 4, 5, 7, 8, 9, 10]

print(‘The missing number is’, getMissingNumber(arr))

Скачать Выполнить код

результат:

The missing number is 6

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

Источник

Given an array arr[] of size N-1 with integers in the range of [1, N], the task is to find the missing number from the first N integers.

Note: There are no duplicates in the list.

Examples:

Input: arr[] = {1, 2, 4, 6, 3, 7, 8}, N = 8
Output: 5
Explanation: The missing number between 1 to 8 is 5

Input: arr[] = {1, 2, 3, 5}, N = 5
Output: 4
Explanation: The missing number between 1 to 5 is 4

Approach 1 (Using Hashing): The idea behind the following approach is

The numbers will be in the range (1, N), an array of size N can be maintained to keep record of the elements present in the given array

Create a temp array temp[] of size n + 1 with all initial values as 0.
Traverse the input array arr[], and do following for each arr[i]
- if(temp[arr[i]] == 0) temp[arr[i]] = 1
Traverse temp[] and output the array element having value as 0 (This is the missing element).

Below is the implementation of the above approach:

C

#include <stdio.h>

void findMissing(int arr[], int N)

{

int temp[N + 1];

for (int i = 0; i <= N; i++) {

temp[i] = 0;

}

for (int i = 0; i < N; i++) {

temp[arr[i] - 1] = 1;

}

int ans;

for (int i = 0; i <= N; i++) {

if (temp[i] == 0)

ans = i + 1;

}

printf("%d", ans);

}

int main()

{

int arr[] = { 1, 3, 7, 5, 6, 2 };

int n = sizeof(arr) / sizeof(arr[0]);

findMissing(arr, n);

}

C++

#include <bits/stdc++.h>

using namespace std;

void findMissing(int arr[], int N)

{

int i;

int temp[N + 1];

for(int i = 0; i <= N; i++){

temp[i] = 0;

}

for(i = 0; i < N; i++){

temp[arr[i] - 1] = 1;

}

int ans;

for (i = 0; i <= N ; i++) {

if (temp[i] == 0)

ans = i + 1;

}

cout << ans;

}

int main()

{

int arr[] = { 1, 3, 7, 5, 6, 2 };

int n = sizeof(arr) / sizeof(arr[0]);

findMissing(arr, n);

}

Java

import java.io.*;

import java.util.*;

class GFG {

public static void findMissing(int arr[], int N)

{

int i;

int temp[] = new int[N + 1];

for (i = 0; i <= N; i++) {

temp[i] = 0;

}

for (i = 0; i < N; i++) {

temp[arr[i] - 1] = 1;

}

int ans = 0;

for (i = 0; i <= N; i++) {

if (temp[i] == 0)

ans = i + 1;

}

System.out.println(ans);

}

public static void main(String[] args)

{

int arr[] = { 1, 3, 7, 5, 6, 2 };

int n = arr.length;

findMissing(arr, n);

}

Python3

def findMissing(arr, N):

temp = [0] * (N+1)

for i in range(0, N):

temp[arr[i] - 1] = 1

for i in range(0, N+1):

if(temp[i] == 0):

ans = i + 1

print(ans)

if __name__ == '__main__':

arr = [1, 2, 3, 5]

N = len(arr)

findMissing(arr, N)

C#

using System;

public class GFG {

public static void findMissing(int[] arr, int N)

{

int[] temp = new int[N + 1];

for (int i = 0; i < N; i++) {

temp[arr[i] - 1] = 1;

}

int ans = 0;

for (int i = 0; i <= N; i++) {

if (temp[i] == 0)

ans = i + 1;

}

Console.WriteLine(ans);

}

static public void Main()

{

int[] arr = { 1, 3, 7, 5, 6, 2 };

int n = arr.Length;

findMissing(arr, n);

}

Javascript

<script>

function findMissing(arr,N){

let i;

let temp = [];

for (i = 0; i <= N; i++) {

temp[i] = 0;

}

for (i = 0; i < N; i++) {

temp[arr[i] - 1] = 1;

}

let ans = 0;

for (i = 0; i <= N; i++) {

if (temp[i] == 0)

ans = i + 1;

}

console.log(ans);

}

let arr = [ 1, 3, 7, 5, 6, 2 ];

let n = arr.length;

findMissing(arr,n);

</script>

Time Complexity: O(N)
Auxiliary Space: O(N)

Approach 2 (Using summation of first N natural numbers): The idea behind the approach is to use the summation of the first N numbers.

Find the sum of the numbers in the range [1, N] using the formula N * (N+1)/2. Now find the sum of all the elements in the array and subtract it from the sum of the first N natural numbers. This will give the value of the missing element.

Follow the steps mentioned below to implement the idea:

Calculate the sum of the first N natural numbers as sumtotal= N*(N+1)/2.
Traverse the array from start to end.
- Find the sum of all the array elements.
Print the missing number as SumTotal – sum of array

Below is the implementation of the above approach:

C

#include <stdio.h>

int getMissingNo(int a[], int n)

{

int i, total;

total = (n + 1) * (n + 2) / 2;

for (i = 0; i < n; i++)

total -= a[i];

return total;

}

void main()

{

int arr[] = { 1, 2, 3, 5 };

int N = sizeof(arr) / sizeof(arr[0]);

int miss = getMissingNo(arr, N);

printf("%d", miss);

}

C++14

#include <bits/stdc++.h>

using namespace std;

int getMissingNo(int a[], int n)

{

int N = n + 1;

int total = (N) * (N + 1) / 2;

for (int i = 0; i < n; i++)

total -= a[i];

return total;

}

int main()

{

int arr[] = { 1, 2, 3, 5 };

int N = sizeof(arr) / sizeof(arr[0]);

int miss = getMissingNo(arr, N);

cout << miss;

return 0;

}

Java

import java.util.*;

import java.util.Arrays;

class GFG {

public static int getMissingNo(int[] nums, int n)

{

int sum = ((n + 1) * (n + 2)) / 2;

for (int i = 0; i < n; i++)

sum -= nums[i];

return sum;

}

public static void main(String[] args)

{

int[] arr = { 1, 2, 3, 5 };

int N = arr.length;

System.out.println(getMissingNo(arr, N));

}

Python

def getMissingNo(arr, n):

total = (n + 1)*(n + 2)/2

sum_of_A = sum(arr)

return total - sum_of_A

if __name__ == '__main__':

arr = [1, 2, 3, 5]

N = len(arr)

miss = getMissingNo(arr, N)

print(miss)

C#

using System;

class GFG {

static int getMissingNo(int[] a, int n)

{

int total = (n + 1) * (n + 2) / 2;

for (int i = 0; i < n; i++)

total -= a[i];

return total;

}

public static void Main()

{

int[] arr = { 1, 2, 3, 5 };

int N = 4;

int miss = getMissingNo(arr, N);

Console.Write(miss);

}

PHP

<?php

function getMissingNo ($a, $n)

{

$total = ($n + 1) * ($n + 2) / 2;

for ( $i = 0; $i < $n; $i++)

$total -= $a[$i];

return $total;

}

$arr = array(1, 2, 3, 5);

$N = 4;

$miss = getMissingNo($arr, $N);

echo($miss);

?>

Javascript

<script>

function getMissingNo(a, n) {

let total = Math.floor((n + 1) * (n + 2) / 2);

for (let i = 0; i < n; i++)

total -= a[i];

return total;

}

let arr = [ 1, 2, 3, 5 ];

let N = arr.length;

let miss = getMissingNo(arr, N);

document.write(miss);

</script>

Time Complexity: O(N)
Auxiliary Space: O(1)

Modification for Overflow: The approach remains the same but there can be an overflow if N is large.

In order to avoid integer overflow, pick one number from the range [1, N] and subtract a number from the given array (don’t subtract the same number twice). This way there won’t be any integer overflow.

Algorithm:

Create a variable sum = 1 which will store the missing number and a counter variable c = 2.
Traverse the array from start to end.
- Update the value of sum as sum = sum – array[i] + c and increment c by 1. This performs the task mentioned in the above idea]
Print the missing number as a sum.

Below is the implementation of the above approach:

C

#include <stdio.h>

int getMissingNo(int a[], int n)

{

int i, total = 1;

for (i = 2; i < (n + 1); i++) {

total += i;

total -= a[i - 2];

}

return total;

}

void main()

{

int arr[] = { 1, 2, 3, 5 };

int N = sizeof(arr) / sizeof(arr[0]);

printf("%d", getMissingNo(arr, N));

}

C++14

#include <bits/stdc++.h>

using namespace std;

int getMissingNo(int a[], int n)

{

int i, total = 1;

for (i = 2; i < (n + 1); i++) {

total += i;

total -= a[i - 2];

}

return total;

}

int main()

{

int arr[] = { 1, 2, 3, 5 };

int N = sizeof(arr) / sizeof(arr[0]);

cout << getMissingNo(arr, N);

return 0;

}

Java

class GFG {

static int getMissingNo(int a[], int n)

{

int total = 1;

for (int i = 2; i < (n + 1); i++) {

total += i;

total -= a[i - 2];

}

return total;

}

public static void main(String[] args)

{

int[] arr = { 1, 2, 3, 5 };

int N = arr.length;

System.out.println(getMissingNo(arr, N));

}

Python3

def getMissingNo(a, n):

i, total = 0, 1

for i in range(2, n + 2):

total += i

total -= a[i - 2]

return total

if __name__ == '__main__':

arr = [1, 2, 3, 5]

N = len(arr)

print(getMissingNo(arr, N))

C#

using System;

class GFG {

static int getMissingNo(int[] a, int n)

{

int i, total = 1;

for (i = 2; i < (n + 1); i++) {

total += i;

total -= a[i - 2];

}

return total;

}

public static void Main()

{

int[] arr = { 1, 2, 3, 5 };

int N = (arr.Length);

Console.Write(getMissingNo(arr, N));

}

Javascript

<script>

function getMissingNo(a, n)

{

let i, total=1;

for (i = 2; i< (n+1); i++)

{

total += i;

total -= a[i-2];

}

return total;

}

let arr = [1, 2, 3, 5];

let N = arr.length;

document.write(getMissingNo(arr, N));

</script>

Time Complexity: O(N). Only one traversal of the array is needed.
Auxiliary Space: O(1). No extra space is needed

Approach 3 (Using binary operations): This method uses the technique of XOR to solve the problem.

XOR has certain properties

Assume a₁ ⊕ a₂ ⊕ a₃ ⊕ . . . ⊕ a_n = a and a₁ ⊕ a₂ ⊕ a₃ ⊕ . . . ⊕ a_n-1 = b

Then a ⊕ b = a_n

Follow the steps mentioned below to implement the idea:

Create two variables a = 0 and b = 0
Run a loop from i = 1 to N:
- For every index, update a as a = a ^ i
Now traverse the array from i = start to end.
- For every index, update b as b = b ^ arr[i].
The missing number is a ^ b.

Below is the implementation of the above approach:

C

#include <stdio.h>

int getMissingNo(int a[], int n)

{

int i;

int x1 = a[0];

int x2 = 1;

for (i = 1; i < n; i++)

x1 = x1 ^ a[i];

for (i = 2; i <= n + 1; i++)

x2 = x2 ^ i;

return (x1 ^ x2);

}

void main()

{

int arr[] = { 1, 2, 3, 5 };

int N = sizeof(arr) / sizeof(arr[0]);

int miss = getMissingNo(arr, N);

printf("%d", miss);

}

C++

#include <bits/stdc++.h>

using namespace std;

int getMissingNo(int a[], int n)

{

int x1 = a[0];

int x2 = 1;

for (int i = 1; i < n; i++)

x1 = x1 ^ a[i];

for (int i = 2; i <= n + 1; i++)

x2 = x2 ^ i;

return (x1 ^ x2);

}

int main()

{

int arr[] = { 1, 2, 3, 5 };

int N = sizeof(arr) / sizeof(arr[0]);

int miss = getMissingNo(arr, N);

cout << miss;

return 0;

}

Java

class Main {

static int getMissingNo(int a[], int n)

{

int x1 = a[0];

int x2 = 1;

for (int i = 1; i < n; i++)

x1 = x1 ^ a[i];

for (int i = 2; i <= n + 1; i++)

x2 = x2 ^ i;

return (x1 ^ x2);

}

public static void main(String args[])

{

int arr[] = { 1, 2, 3, 5 };

int N = arr.length;

int miss = getMissingNo(arr, N);

System.out.println(miss);

}

Python3

def getMissingNo(a, n):

x1 = a[0]

x2 = 1

for i in range(1, n):

x1 = x1 ^ a[i]

for i in range(2, n + 2):

x2 = x2 ^ i

return x1 ^ x2

if __name__ == '__main__':

arr = [1, 2, 3, 5]

N = len(arr)

miss = getMissingNo(arr, N)

print(miss)

C#

using System;

class GFG {

static int getMissingNo(int[] a, int n)

{

int x1 = a[0];

int x2 = 1;

for (int i = 1; i < n; i++)

x1 = x1 ^ a[i];

for (int i = 2; i <= n + 1; i++)

x2 = x2 ^ i;

return (x1 ^ x2);

}

public static void Main()

{

int[] arr = { 1, 2, 3, 5 };

int N = 4;

int miss = getMissingNo(arr, N);

Console.Write(miss);

}

PHP

<?php

function getMissingNo($a, $n)

{

$x1 = $a[0];

$x2 = 1;

for ($i = 1; $i < $n; $i++)

$x1 = $x1 ^ $a[$i];

for ($i = 2; $i <= $n + 1; $i++)

$x2 = $x2 ^ $i;

return ($x1 ^ $x2);

}

$arr = array(1, 2, 3, 5);

$N = 4;

$miss = getMissingNo($arr, $N);

echo($miss);

?>

Javascript

<script>

function getMissingNo(a, n)

{

var x1 = a[0];

var x2 = 1;

for (var i = 1; i < n; i++) x1 = x1 ^ a[i];

for (var i = 2; i <= n + 1; i++) x2 = x2 ^ i;

return x1 ^ x2;

}

var arr = [1, 2, 3, 5];

var N = arr.length;

var miss = getMissingNo(arr, N);

document.write(miss);

</script>

Time Complexity: O(N)
Auxiliary Space: O(1)

Approach 4 (Using Cyclic Sort): The idea behind it is as follows:

All the given array numbers are sorted and in the range of 1 to n-1. If the range is 1 to N then the index of every array element will be the same as (value – 1).

Follow the below steps to implement the idea:

Use cyclic sort to sort the elements in linear time.
Now traverse from i = 0 to the end of the array:
- If arr[i] is not the same as i+1 then the missing element is (i+1).
If all elements are present then N is the missing element in the range [1, N].

Below is the implementation of the above approach.

C

#include <stdio.h>

int getMissingNo(int a[], int n)

{

int i = 0;

while (i < n) {

int correct = a[i] - 1;

if (a[i] < n && a[i] != a[correct]) {

int temp = a[i];

a[i] = a[correct];

a[correct] = temp;

}

else {

i++;

}

for (int i = 0; i < n; i++) {

if (i != a[i] - 1) {

return i + 1;

}

return n;

}

int main()

{

int arr[] = { 1, 2, 3, 5 };

int N = sizeof(arr) / sizeof(arr[0]);

int miss = getMissingNo(arr, N);

printf("%d", miss);

return 0;

}

C++

#include <bits/stdc++.h>

using namespace std;

int getMissingNo(int a[], int n)

{

int i = 0;

while (i < n) {

int correct = a[i] - 1;

if (a[i] < n && a[i] != a[correct]) {

swap(a[i], a[correct]);

}

else {

i++;

}

for (int i = 0; i < n; i++) {

if (i != a[i] - 1) {

return i + 1;

}

return n;

}

int main()

{

int arr[] = { 1, 2, 3, 5 };

int N = sizeof(arr) / sizeof(arr[0]);

int miss = getMissingNo(arr, N);

cout << (miss);

return 0;

}

Java

import java.util.*;

public class MissingNumber {

public static void main(String[] args)

{

int[] arr = { 1, 2, 3, 5 };

int N = arr.length;

int ans = getMissingNo(arr, N);

System.out.println(ans);

}

static int getMissingNo(int[] arr, int n)

{

int i = 0;

while (i < n) {

int correctpos = arr[i] - 1;

if (arr[i] < n && arr[i] != arr[correctpos]) {

swap(arr, i, correctpos);

}

else {

i++;

}

for (int index = 0; index < arr.length; index++) {

if (arr[index] != index + 1) {

return index + 1;

}

return arr.length;

}

static void swap(int[] arr, int i, int correctpos)

{

int temp = arr[i];

arr[i] = arr[correctpos];

arr[correctpos] = temp;

}

Python3

def getMissingNo(arr, n) :

i = 0;

while (i < n) :

correctpos = arr[i] - 1;

if (arr[i] < n and arr[i] != arr[correctpos]) :

arr[i],arr[correctpos] = arr[correctpos], arr[i]

else :

i += 1;

for index in range(n) :

if (arr[index] != index + 1) :

return index + 1;

return n;

if __name__ == "__main__" :

arr = [ 1, 2, 3, 5 ];

N = len(arr);

print(getMissingNo(arr, N));

C#

using System;

class GFG {

static int getMissingNo(int[] arr, int n)

{

int i = 0;

while (i < n) {

int correctpos = arr[i] - 1;

if (arr[i] < n && arr[i] != arr[correctpos]) {

swap(arr, i, correctpos);

}

else {

i++;

}

for (int index = 0; index < n; index++) {

if (arr[index] != index + 1) {

return index + 1;

}

return n;

}

static void swap(int[] arr, int i, int correctpos)

{

int temp = arr[i];

arr[i] = arr[correctpos];

arr[correctpos] = temp;

}

public static void Main()

{

int[] arr = { 1, 2, 4, 5, 6 };

int N = arr.Length;

int ans = getMissingNo(arr, N);

Console.Write(ans);

}

Javascript

<script>

var arr = [ 1, 2, 3, 5 ];

var N = arr.length;

var ans = getMissingNo(arr, N);

console.log(ans);

function getMissingNo(arr, n)

{

var i = 0;

while (i < n) {

var correctpos = arr[i] - 1;

if (arr[i] < n && arr[i] != arr[correctpos]) {

swap(arr, i, correctpos);

}

else {

i++;

}

for (var index = 0; index < arr.length; index++) {

if (arr[index] != index + 1) {

return index + 1;

}

return n;

}

function swap(arr, i, correctpos)

{

var temp = arr[i];

arr[i] = arr[correctpos];

arr[correctpos] = temp;

}

</script>

Time Complexity: O(N), requires (N-1) comparisons
Auxiliary Complexity: O(1)

Approach 5 (Use elements as Index and mark the visited places as negative): Use the below idea to get the approach

Traverse the array. While traversing, use the absolute value of every element as an index and make the value at this index as negative to mark it visited. To find missing, traverse the array again and look for a positive value.

Follow the steps to solve the problem:

Traverse the given array
- If the absolute value of current element is greater than size of the array, then continue.
- else multiply the (absolute value of (current element) – 1)th index with -1.
Initialize a variable ans = size + 1.
Traverse the array and follow the steps:
- if the value is positive assign ans = index + 1
Print ans as the missing value.

Below is the implementation of the above approach:

C

#include <stdio.h>

#include <stdlib.h>

void findMissing(int arr[], int size)

{

int i;

for (i = 0; i < size; i++) {

if (abs(arr[i]) - 1 == size) {

continue;

}

int ind = abs(arr[i]) - 1;

arr[ind] *= -1;

}

int ans = size + 1;

for (i = 0; i < size; i++) {

if (arr[i] > 0)

ans = i + 1;

}

printf("%d", ans);

}

int main()

{

int arr[] = { 1, 3, 7, 5, 6, 2 };

int n = sizeof(arr) / sizeof(arr[0]);

findMissing(arr, n);

return 0;

}

C++

#include <bits/stdc++.h>

using namespace std;

void findMissing(int arr[], int size)

{

int i;

for (i = 0; i < size; i++) {

if(abs(arr[i]) - 1 == size){

continue;

}

int ind = abs(arr[i]) - 1;

arr[ind] *= -1;

}

int ans = size + 1;

for (i = 0; i < size; i++) {

if (arr[i] > 0)

ans = i + 1;

}

cout << ans;

}

int main()

{

int arr[] = { 1, 3, 7, 5, 6, 2 };

int n = sizeof(arr) / sizeof(arr[0]);

findMissing(arr, n);

}

Java

import java.io.*;

import java.util.*;

class GFG {

public static void findMissing(int arr[], int size)

{

int i;

for (i = 0; i < size; i++) {

if (Math.abs(arr[i]) - 1 == size) {

continue;

}

int ind = Math.abs(arr[i]) - 1;

arr[ind] *= -1;

}

int ans = size + 1;

for (i = 0; i < size; i++) {

if (arr[i] > 0)

ans = i + 1;

}

System.out.println(ans);

}

public static void main(String[] args)

{

int arr[] = { 1, 3, 7, 5, 6, 2 };

int n = arr.length;

findMissing(arr, n);

}

Python3

def findMissing(a, size):

for i in range(0, n):

if (abs(arr[i]) - 1 == size):

continue

ind = abs(arr[i]) - 1

arr[ind] *= -1

ans = size + 1

for i in range(0, n):

if (arr[i] > 0):

ans = i + 1

print(ans)

if __name__ == '__main__':

arr = [1, 3, 7, 5, 6, 2]

n = len(arr)

findMissing(arr, n)

C#

using System;

public class GFG {

public static void findMissing(int[] arr, int size)

{

for (int i = 0; i < size; i++) {

if (Math.Abs(arr[i]) - 1 == size)

continue;

int ind = Math.Abs(arr[i]) - 1;

arr[ind] *= -1;

}

int ans = size + 1;

for (int i = 0; i < size; i++) {

if (arr[i] > 0)

ans = i + 1;

}

Console.WriteLine(ans);

}

static public void Main()

{

int[] arr = { 1, 3, 7, 5, 6, 2 };

int n = arr.Length;

findMissing(arr, n);

}

Javascript

<script>

function findMissing(arr,size){

let i;

for (i = 0; i < size; i++) {

if (Math.abs(arr[i]) - 1 == size) {

continue;

}

let ind = Math.abs(arr[i]) - 1;

arr[ind] *= -1;

}

let ans = size + 1;

for (i = 0; i < size; i++) {

if (arr[i] > 0)

ans = i + 1;

}

console.log(ans);

}

let arr = [ 1, 3, 7, 5, 6, 2 ];

let n = arr.length;

findMissing(arr,n);

</script>

Time Complexity: O(N)
Auxiliary Space: O(1)

Last Updated :
25 Apr, 2023

Like Article

Save Article

Источник

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

Желаю удачи в решении!

Задание первое

Задание второе

Благодарю за внимание!

Задача: найти недостающий элемент массива

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

C

Java

Python

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

C

Java

Python

C

C++

Java

Python3

C#

Javascript

C

C++14

Java

Python

C#

PHP

Javascript

C

C++14

Java

Python3

C#

Javascript

C

C++

Java

Python3

C#

PHP

Javascript

C

C++

Java

Python3

C#

Javascript

C

C++

Java

Python3

C#

Javascript

Вам также может понравиться

Как найти единственно любимого человека

Как нас найти греческая 1

Как найти по ипу

Добавить комментарий Отменить ответ

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