Пронађите једини понављајући елемент између 1 до Н-1  


Ниво тешкоће Лако
Често питани у ЦоупонДуниа Делхивери ГреиОранге Инфо Едге ЛинкедИн Нагарро САП Лабс
Ред Хасх Претраживање

Проналазећи једини понављајући елемент између 1 до Н-1 проблема дали смо поредак случајних целих бројева у опсегу од 1 до н-1. Биће један број који се понавља. Ваш задатак је да пронађете тај број.

Пример  

Улазни

[2,3,4,5,2,1] А.

Излаз

2

Објашњење

2 је елемент који долази два пута у низу.

 

Алгоритам за проналажење јединог понављајућег елемента између 1 и Н-1  

  1. Подесите зброј на 0.
  2. Док је и <н, пређите читав низ.
    1. Збир = збир + арр [и].
  3. Повратна сума- (н * (н-1)) / 2.

Објашњење за проналазак јединог понављајућег елемента између 1 до Н-1  

Дали смо изјаву о проблему (Пронађи једини понављајући елемент између 1 до Н-1) која тражи да се сазна онај број који се понавља у низу. Једноставно ћемо користити Формула суме. Коришћење Сум формула, лако можемо идентификовати поновљени елемент. Као и по имену то и упознајемо Формула суме значи једноставно сумирање вредности.

Ми овде у петљи почињемо да прелазимо низ од 0. позиције до краја петље док не посетимо последњи елемент низа. Са сваком итерацијом и за сваку вредност низа [и] додаћемо је са сумом и складиштити у суму тако да када следећи пут пређемо преко ње добијемо сумирану вредност, а не иницијализовану вредност суме као 0. Дакле, у свакој итерацији имамо неке вредности у њој ускладиштене као збир.

Види такође
Укупан број без поновљених цифара у опсегу

Само треба да направимо формулу која даје поновљени елемент или можемо рећи да само враћа додатни елемент који долази у низу. Претпоставимо да имамо низ који се од 1 до 5 даје непрекидно, када саберемо све бројеве који дају зброј свих бројева и без поновљеног елемента у низу. И враћамо разлику у збиру - (н * (н-1)) / 2, што је наша формула збира.

Размотримо пример:

арр = [2,3,4,5,2,1], сума = 0

Почевши од 0, можемо прећи целу петљу у посети сваком елементу ->

и = 0;

сума = сума + арр [и] => сума = 2

и = 1;

сума = сума + арр [и] => сума = 5

и = 2;

сума = сума + арр [и] => сума = 9

и = 3;

сума = сума + арр [и] => сума = 14

и = 4;

сума = сума + арр [и] => сума = 16

и = 5;

сума = сума + арр [и] => сума = 17

и ми само враћамо сум- (н * (н-1)) / 2 који је 17- (6 * (6-1)) / 2.

17 - 15 = 2, што је наш потребан излаз.

 

Пронађите једини понављајући елемент између 1 до Н-1Пин

Примена у проналажењу јединог понављајућег елемента између 1 и Н-1  

Програм Ц ++

#include<iostream>
using namespace std;
int getRepeatedElement(int arr[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum = sum + arr[i];
    }
    return sum-(((n - 1) * n)/2);
}
int main()
{
    int arr[] = {1,5,3,2,6,4,7,8,4};
    int len = sizeof(arr)/sizeof(arr[0]);
    cout<<(getRepeatedElement(arr, len));
    return 0;
}
4

Јава Програм

class repetitiveElement
{
    public static int getRepeatedElement(int[] arr, int n)
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum = sum + arr[i];
        }
        return sum-(((n - 1) * n)/2);
    }
    public static void main(String args[])
    {
        int[] arr = {1,5,3,2,6,4,7,8,4};
        int len = arr.length;
        System.out.println(getRepeatedElement(arr, len));
    }
}
4

Анализа сложености за проналажење јединог понављајућег елемента између 1 и Н-1  

Сложеност времена

Он) где „Н“ је број елемената у низу.

Сложеност простора

О (1) јер овде не користимо никакав помоћни простор.

Види такође
Клизни прозор максимум

Референце