Рубрики

Проверьте, являются ли элементы массива последовательными во времени O (n) и пространстве O (1) (обрабатывает как положительные, так и отрицательные числа)

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

Input : arr[] = {5, 4, 2, 1, 3}
Output : Yes

Input : arr[] = {2, 1, 0, -3, -1, -2}
Output : Yes

Мы обсудили три различных подхода в посте ниже

Проверьте, являются ли элементы массива последовательными

В вышеприведенном посте. три метода для этой проблемы обсуждаются с лучшей временной сложностью O (n) и в O (1) дополнительном пространстве, но это решение не обрабатывает случай отрицательных чисел. Итак, в этом посте будет обсуждаться метод с временной сложностью O (n) и использованием пространства O (1), который также будет обрабатывать отрицательный случай. Важным предположением здесь является то, что элементы различны.

  1. Найти сумму массива.
  2. Если данные элементы массива являются последовательными, это означает, что они находятся в AP. Итак, найдите элемент min, т.е. первый член AP, затем вычислите ap_sum = n / 2 * [2a + (n-1) * d], где d = 1. Итак, ap_sum = n / 2 * [2a + (n-1) ]
  3. Сравните обе суммы. Распечатать Да, если равно, иначе Нет.

C ++

// C ++ программа для реализации выше
#include <bits/stdc++.h>

using namespace std;

  
// Функция для проверки последовательности элементов

bool areConsecutives(int arr[], int n)

{

    // Найти минимальный элемент в массиве

    int first_term = *(min_element(arr, arr + n));

  

    // Рассчитать сумму AP

    int ap_sum = (n * (2 * first_term + (n - 1) * 1)) / 2;

  

    // Рассчитать заданную сумму массива

    int arr_sum = 0;

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

        arr_sum += arr[i];

  

    // Сравнение сумм и возврата

    return ap_sum == arr_sum;

}

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

int main()

{

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

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

  

    areConsecutives(arr, n) ? cout << "Yes"

                            : cout << "No";

  

    return 0;

}

Джава

// Java-программа для проверки наличия элементов массива
// последовательны

import java.io.*;

  

class GFG {

  

    // Функция для проверки, если элементы

    // последовательный

    static Boolean areConsecutives(int arr[],

                                      int n)

    {

        // Найти минимальный элемент в массиве

        int first_term = Integer.MAX_VALUE;

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

        {

            if(arr[j] < first_term)

            first_term = arr[j];

        }

  

        // Рассчитать сумму AP

        int ap_sum = (n * (2 * first_term +

                         (n - 1) * 1)) / 2;

  

        // Рассчитать заданную сумму массива

        int arr_sum = 0;

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

            arr_sum += arr[i];

  

        // Сравнение сумм и возврата

        return ap_sum == arr_sum;

    }

  

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

    public static void main(String[] args)

    {

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

    int n = arr.length;

      

    Boolean result = areConsecutives(arr, n);

    if(result == true)

    System.out.println("Yes");

    else

    System.out.println("No");

  

    }

}
// Этот код предоставлен Prerna Saini

Python 3

# Программа Python 3 для выше
# реализация

import sys

  
# Функция для проверки наличия элементов
# являются последовательными

def areConsecutives(arr, n):

  

    # Найти минимальный элемент в массиве

    first_term = sys.maxsize

    for i in range(n):

        if arr[i] < first_term:

            first_term = arr[i]

  

    # Рассчитать сумму AP

    ap_sum = ((n * (2 * first_term + 

              (n - 1) * 1)) // 2)

  

    # Рассчитать заданную сумму массива

    arr_sum = 0

    for i in range( n):

        arr_sum += arr[i]

  

    # Сравните обе суммы и возврат

    return ap_sum == arr_sum

  
Код водителя

arr = [ 2, 1, 0, -3, -1, -2 ]

n = len(arr)

  

if areConsecutives(arr, n):

    print( "Yes")

else

    print( "No")

  
# Этот код добавлен
# by ChitraNayal

C #

// C # программа для проверки наличия массива
// элементы являются последовательными

using System;

  

class GFG {

  

    // Функция для проверки наличия элементов

    // последовательны

    static bool areConsecutives(int []arr,

                                int n)

    {

          

        // Найти минимальный элемент в массиве

        int first_term = int.MaxValue;

          

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

        {

            if(arr[j] < first_term)

            first_term = arr[j];

        }

  

        // Рассчитать сумму AP

        int ap_sum = (n * (2 * first_term +

                     (n - 1) * 1)) / 2;

  

        // Рассчитать заданную сумму массива

        int arr_sum = 0;

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

            arr_sum += arr[i];

  

        // Сравнение сумм и возврата

        return ap_sum == arr_sum;

    }

  

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

    public static void Main()

    {

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

        int n = arr.Length;

          

        bool result = areConsecutives(arr, n);

        if(result == true)

        Console.WriteLine("Yes");

        else

        Console.WriteLine("No");

  

    }

}

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

PHP

<?php
// PHP программа для проверки
// элементы массива являются последовательными

  
// Функция для проверки наличия элементов
// последовательны

function areConsecutives($arr, $n)

{

      

    // Найти минимальный элемент в массиве

    $first_term = 9999999;

      

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

    {

        if($arr[$j] < $first_term)

            $first_term = $arr[$j];

    }

  

    // Рассчитать сумму AP

    $ap_sum = intval(($n * (2 * $first_term

                         ($n - 1) * 1)) / 2);

  

    // Рассчитать заданную сумму массива

    $arr_sum = 0;

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

        $arr_sum += $arr[$i];

  

    // Сравнение сумм и возврата

    return $ap_sum == $arr_sum;

}

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

$arr = array(2, 1, 0, -3, -1, -2);

$n = count($arr);

  

$result = areConsecutives($arr, $n);

if($result == true)

echo "Yes";

else

echo "No";

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


Выход :

Yes

Сложность времени: O (n)
Вспомогательное пространство: O (1)

Эта статья предоставлена Сахилом Чхаброй . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Проверьте, являются ли элементы массива последовательными во времени O (n) и пространстве O (1) (обрабатывает как положительные, так и отрицательные числа)

0.00 (0%) 0 votes