Рубрики

Найдите недостающее число в Арифметической прогрессии

Дан массив, представляющий элементы арифметической прогрессии по порядку. Один элемент отсутствует в прогрессии, найдите пропущенный номер.

Примеры:

Input: arr[]  = {2, 4, 8, 10, 12, 14}
Output: 6

Input: arr[]  = {1, 6, 11, 16, 21, 31};
Output: 26

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

Мы можем решить эту проблему за O (Logn) время, используя бинарный поиск . Идея состоит в том, чтобы перейти к среднему элементу. Проверьте, равна ли разница между серединой и рядом с серединой различием или нет, если нет, то отсутствующий элемент находится между серединой и серединой + 1. Если средний элемент равен n / 2- му члену в арифметической серии (пусть n будет количеством элементов во входном массиве), то отсутствующий элемент находится в правой половине. Остальной элемент лежит в левой половине.

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для поиска недостающего номера
// в заданной арифметической прогрессии
#include<iostream>

using namespace std;

#define INT_MAX 2147483647;

class GFG

{

      
// рекурсивная функция на основе бинарного поиска, которая возвращает
// недостающий элемент в арифметической прогрессии

public:int findMissingUtil(int arr[], int low, 

                           int high, int diff)

{

    // Должно быть два элемента, чтобы найти недостающее

    if (high <= low)

        return INT_MAX;

  

    // Найти индекс среднего элемента

    int mid = low + (high - low) / 2;

  

    // Элемент сразу после среднего элемента отсутствует.

    // arr [mid + 1] должен существовать, потому что мы возвращаемся, когда

    // (низкий == высокий) и взять слово (высокий-низкий) / 2

    if (arr[mid + 1] - arr[mid] != diff)

        return (arr[mid] + diff);

  

    // Элемент перед серединой отсутствует

    if (mid > 0 && arr[mid] - arr[mid - 1] != diff)

        return (arr[mid - 1] + diff);

  

    // Если элементы до середины следуют за AP, то повторяются

    // для правой половины

    if (arr[mid] == arr[0] + mid * diff)

        return findMissingUtil(arr, mid + 1, 

                               high, diff);

  

    // Остальное повторяется для левой половины

    return findMissingUtil(arr, low, mid - 1, diff);

}

  
// Функция использует findMissingUtil () для
// найти недостающий элемент в AP.
// Предполагается, что есть ровно один
// отсутствует элемент и может дать неверный результат
// когда отсутствует отсутствующий элемент или
// более одного недостающего элемента. Эта функция
// также предполагает, что разница в AP
// целое число

int findMissing(int arr[], int n) 

{

    // Если отсутствует только один элемент, то мы можем найти

    // разница арифметической прогрессии с использованием следующего

    // формула Пример 2, 4, 6, 10, diff = (10-2) / 4 = 2.

    // В формуле предполагается, что разница

    // целое число

    int diff = (arr[n - 1] - arr[0]) / n;

  

    // Двоичный поиск пропавших

    // число, использующее вычисленный выше diff

    return findMissingUtil(arr, 0, n - 1, diff);

}
};

  
// Код драйвера

int main()

{

    GFG g;

    int arr[] = {2, 4, 8, 10, 12, 14};

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

    cout << "The missing element is " 

         << g.findMissing(arr, n);

    return 0;

  
// Этот код предоставлен Soumik

С

// AC программа для поиска пропущенного числа в данном
// арифметическая прогрессия
#include <stdio.h>
#include <limits.h>

  
// рекурсивная функция на основе бинарного поиска, которая возвращает
// недостающий элемент в арифметической прогрессии

int findMissingUtil(int arr[], int low, int high, int diff)

{

    // Должно быть два элемента, чтобы найти недостающее

    if (high <= low)

        return INT_MAX;

  

    // Найти индекс среднего элемента

    int mid = low + (high - low)/2;

  

    // Элемент сразу после среднего элемента отсутствует.

    // arr [mid + 1] должен существовать, потому что мы возвращаемся, когда

    // (низкий == высокий) и взять слово (высокий-низкий) / 2

    if (arr[mid+1] - arr[mid] != diff)

        return (arr[mid] + diff);

  

    // Элемент перед серединой отсутствует

    if (mid > 0 && arr[mid] - arr[mid-1] != diff)

        return (arr[mid-1] + diff);

  

    // Если элементы до середины следуют за AP, то повторяются

    // для правой половины

    if (arr[mid] == arr[0] + mid*diff)

        return findMissingUtil(arr, mid+1, high, diff);

  

    // Остальное повторяется для левой половины

    return findMissingUtil(arr, low, mid-1, diff);

}

  
// Функция использует findMissingUtil (), чтобы найти недостающие
// элемент в AP. Предполагается, что отсутствует только один
// элемент и может дать неверный результат, если нет пропущенных
// элемент или несколько пропущенных элементов.
// Эта функция также предполагает, что разница в AP
// целое число

int findMissing(int arr[], int n)

{

    // Если отсутствует только один элемент, то мы можем найти

    // разница арифметической прогрессии с использованием следующего

    // формула Пример 2, 4, 6, 10, diff = (10-2) / 4 = 2.

    // В формуле предполагается, что разница

    // целое число

    int diff = (arr[n-1] - arr[0])/n;

  

    // Двоичный поиск пропущенного числа, используя выше

    // вычисляем разницу

    return findMissingUtil(arr, 0, n-1, diff);

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    int arr[] = {2, 4, 8, 10, 12, 14};

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

    printf("The missing element is %d", findMissing(arr, n));

    return 0;

}

Джава

// Java-программа для поиска
// пропущенный номер в
// заданная арифметика
// прогрессия

import java.io.*;

  

class GFG 

{

      
// Бинарный поиск на основе
// рекурсивная функция, которая
// возвращает недостающее
// элемент в арифметике
// прогрессия

static int findMissingUtil(int arr[], int low, 

                           int high, int diff)

{

    // Должно быть два элемента

    // найти пропавшее

    if (high <= low)

        return Integer.MAX_VALUE;

  

    // Найти индекс

    // средний элемент

    int mid = low + (high - low) / 2;

  

    // Элемент сразу после

    // средний элемент отсутствует.

    // arr [mid + 1] должен существовать,

    // потому что мы возвращаемся когда

    // (низкий == высокий) и принять

    // этаж (хай-лоу) / 2

    if (arr[mid + 1] - arr[mid] != diff)

        return (arr[mid] + diff);

  

    // Элемент просто

    // до середины отсутствует

    if (mid > 0 && arr[mid] - 

                   arr[mid - 1] != diff)

        return (arr[mid - 1] + diff);

  

    // Если элементы до середины следуют

    // AP, затем повторить для правой половины

    if (arr[mid] == arr[0] + mid * diff)

        return findMissingUtil(arr, mid + 1

                               high, diff);

  

    // Остальное повторяется для левой половины

    return findMissingUtil(arr, low, mid - 1, diff);

}

  
// Функция использует findMissingUtil ()
// найти недостающий элемент в AP.
// Предполагается, что там точно
// один недостающий элемент и может дать
// неверный результат, когда нет
// отсутствует элемент или более одного
// недостающие элементы. Эта функция также
// предполагает, что разница в AP
// целое число

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

{

    // Если отсутствует только один элемент,

    // тогда мы можем найти разницу

    // арифметическая прогрессия с использованием

    // следующая формула Пример 2, 4,

    // 6, 10, diff = (10-2) / 4 = 2.

    // Предположение в формуле состоит в том, что

    // разница является целым числом

    int diff = (arr[n - 1] - arr[0]) / n;

  

    // Двоичный поиск пропавших

    // число, использующее вычисленный выше diff

    return findMissingUtil(arr, 0, n - 1, diff);

}

  
// Код драйвера

public static void main (String[] args) 

{

    int arr[] = {2, 4, 8, 10, 12, 14};

    int n = arr.length;

    System.out.println("The missing element is "+   

                            findMissing(arr, n));

}
}

  
// Этот код предоставлен anuj_67.

python3

# Python3 программа для поиска пропавшего
число в данной арифметической прогрессии

import sys

  
# Бинарный поиск на основе рекурсивной функции
# который возвращает отсутствующий элемент в
# арифметическая прогрессия

def findMissingUtil(arr, low, high, diff): 

  

    # Там должно быть два элемента

    # найти пропавших без вести

    if (high <= low): 

        return sys.maxsize; 

  

    # Найти индекс среднего элемента

    mid = int(low + (high - low) / 2); 

  

    # Элемент сразу после середины

    Элемент # отсутствует. Обр [середина + 1]

    # должен существовать, потому что мы возвращаемся, когда

    # (низкий == высокий) и взять слово

    # (хай-лоу) / 2

    if (arr[mid + 1] - arr[mid] != diff): 

        return (arr[mid] + diff); 

  

    # Элемент перед серединой отсутствует

    if (mid > 0 and arr[mid] - 

                    arr[mid - 1] != diff): 

        return (arr[mid - 1] + diff); 

  

    # Если элементы до середины следуют за AP,

    # затем повторить для правой половины

    if (arr[mid] == arr[0] + mid * diff): 

        return findMissingUtil(arr, mid + 1,

                                high, diff); 

  

    # Остальное повторяется для левой половины

    return findMissingUtil(arr, low,

                           mid - 1, diff); 

  
# Функция использует findMissingUtil () для поиска
# недостающий элемент в AP. Предполагается, что
# есть ровно один пропущенный элемент и может
# дать неверный результат, если нет пропавших без вести
# элемент или несколько пропущенных элементов.
# Эта функция также предполагает, что разница
# в AP является целым числом.

def findMissing(arr, n): 

  

    # Если ровно один элемент отсутствует, то

    # мы можем найти разницу арифметики

    # прогрессия по следующей формуле.

    # Пример, 2, 4, 6, 10, diff = (10-2) / 4 = 2.

    # Предположение в формуле заключается в том, что

    # разница - это целое число.

    diff = int((arr[n - 1] - arr[0]) / n); 

  

    # Бинарный поиск по отсутствующему номеру

    # используя выше вычисленный diff

    return findMissingUtil(arr, 0, n - 1, diff); 

  
Код водителя

arr = [2, 4, 8, 10, 12, 14]; 

n = len(arr); 

print("The missing element is",

          findMissing(arr, n)); 

  
# Этот код предоставлен chandan_jnu

C #

// AC # программа для поиска
// пропущенный номер в
// заданная арифметика
// прогрессия

using System;

  

class GFG 

{

      
// Бинарный поиск на основе
// рекурсивная функция, которая
// возвращает недостающее
// элемент в арифметике
// прогрессия

static int findMissingUtil(int []arr, int low, 

                           int high, int diff)

{

    // Должно быть два элемента

    // найти пропавшее

    if (high <= low)

        return int.MaxValue;

  

    // Найти индекс

    // средний элемент

    int mid = low + (high - 

                     low) / 2;

  

    // Элемент сразу после

    // средний элемент отсутствует.

    // arr [mid + 1] должен существовать,

    // потому что мы возвращаемся когда

    // (низкий == высокий) и принять

    // этаж (хай-лоу) / 2

    if (arr[mid + 1] - 

        arr[mid] != diff)

        return (arr[mid] + diff);

  

    // Элемент просто

    // до середины отсутствует

    if (mid > 0 && arr[mid] - 

                   arr[mid - 1] != diff)

        return (arr[mid - 1] + diff);

  

    // Если элементы до середины следуют

    // AP, затем повторить для правой половины

    if (arr[mid] == arr[0] +

               mid * diff)

        return findMissingUtil(arr, mid + 1, 

                               high, diff);

  

    // Остальное повторяется для левой половины

    return findMissingUtil(arr, low, 

                           mid - 1, diff);

}

  
// Функция использует findMissingUtil ()
// найти недостающий элемент
// в AP. Предполагается, что там
// ровно один отсутствующий элемент
// и может дать неверный результат
// когда нет пропущенного элемента
// или более одного отсутствующего элемента.
// Эта функция также предполагает, что
// разница в AP является целым числом.

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

{

    // Если ровно один элемент

    // отсутствует, тогда мы можем

    // найти разницу арифметики

    // прогресс с использованием следующего

    // формула Пример 2, 4, 6, 10,

    // diff = (10-2) / 4 = 2. Предположение

    // в формуле это разница

    // является целым числом

    int diff = (arr[n - 1] - 

                arr[0]) / n;

  

    // Двоичный поиск для

    // пропущенный номер используя

    // выше вычисленной разницы

    return findMissingUtil(arr, 0, 

                           n - 1, diff);

}

  
// Код драйвера

public static void Main () 

{

    int []arr = {2, 4, 8, 

                 10, 12, 14};

    int n = arr.Length;

    Console.WriteLine("The missing element is "

                           findMissing(arr, n));

}
}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP программа для поиска пропавшего
// число в данной арифметической прогрессии

  
// Бинарный поиск на основе рекурсивной функции
// который возвращает отсутствующий элемент в
// арифметическая прогрессия

  

function findMissingUtil($arr, $low, $high, $diff

    // Должно быть два элемента

    // найти недостающее

    if ($high <= $low

        return PHP_INT_MAX; 

  

    // Найти индекс среднего элемента

    $mid = $low + ($high - $low) / 2; 

  

    // Элемент сразу после середины

    // элемент отсутствует. Обр [середина + 1]

    // должен существовать, потому что мы возвращаемся, когда

    // (низкий == высокий) и взять слово (высокий-низкий) / 2

    if ($arr[$mid + 1] - $arr[$mid] != $diff

        return ($arr[$mid] + $diff); 

  

    // Элемент перед серединой отсутствует

    if ($mid > 0 && $arr[$mid] - $arr[$mid - 1] != $diff

        return ($arr[$mid - 1] + $diff); 

  

    // Если элементы до середины следуют за AP,

    // затем повторить для правой половины

    if ($arr[$mid] == $arr[0] + $mid * $diff

        return findMissingUtil($arr, $mid + 1, 

                               $high, $diff); 

  

    // Остальное повторяется для левой половины

    return findMissingUtil($arr, $low, $mid - 1, $diff); 

  
// Функция использует findMissingUtil () для поиска
// недостающий элемент в AP. Предполагается, что
// отсутствует ровно один элемент и может
// выдаем неверный результат, если нет пропущенных
// элемент или несколько пропущенных элементов.
// Эта функция также предполагает, что разница
// в AP это целое число.

function findMissing($arr, $n

    // Если отсутствует только один элемент, то

    // мы можем найти разницу арифметики

    // прогрессия по следующей формуле.

    // Пример, 2, 4, 6, 10, diff = (10-2) / 4 = 2.

    // В формуле предполагается, что

    // разница - это целое число

    $diff = ($arr[$n - 1] - $arr[0]) / $n

  

    // Двоичный поиск пропущенного числа

    // используя выше вычисленный diff

    return findMissingUtil($arr, 0, $n - 1, $diff); 

  
// Код драйвера

$arr = array(2, 4, 8, 10, 12, 14); 

$n = sizeof($arr); 

echo "The missing element is "

         findMissing($arr, $n); 

  
// Этот код предоставлен Sach_Code
?>

Выход:

The missing element is 6

Упражнение:
Решите ту же проблему для геометрических рядов. Какова временная сложность вашего решения? А как насчет серии Фибоначчи?

Эта статья предоставлена Харшитом Агравалом . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найдите недостающее число в Арифметической прогрессии

0.00 (0%) 0 votes