1에서 N-1 사이의 유일한 반복 요소 찾기

난이도 쉽게
자주 묻는 질문 쿠폰 Dunia 배달 그레이 오렌지 정보 가장자리 링크드인 나가로 SAP 연구소
배열 해시 수색조회수 81

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

1에서 N-1 문제 사이의 유일한 반복 요소를 찾기 위해 우리는 정렬 1에서 n-1 사이의 임의의 정수입니다. 반복되는 하나의 숫자가 있습니다. 당신의 임무는 그 번호를 찾는 것입니다.

입력

[2,3,4,5,2,1] A

산출

2

설명

2는 배열에서 두 번 나오는 요소입니다.

 

1에서 N-1 사이의 유일한 반복 요소를 찾기위한 알고리즘

  1. 합계를 0으로 설정합니다.
  2. i <n 인 동안 전체 배열을 횡단합니다.
    1. 합계 = sum + arr [i].
  3. sum- (n * (n-1)) / 2를 반환합니다.

1에서 N-1 사이의 유일한 반복 요소 찾기에 대한 설명

우리는 배열에서 반복되는 숫자를 알아 내도록 요청하는 문제 (Find the Only Repetitive Element Between 1 to N-1) 문을 제공했습니다. 우리는 단순히 합계 공식. 사용 합계 공식, 반복되는 요소를 쉽게 식별 할 수 있습니다. 이름에서 알 수 있듯이 합계 공식 단순히 값을 합산하는 것을 의미합니다.

여기 루프에서 마지막 배열 요소를 방문 할 때까지 0 번째 위치에서 루프의 끝까지 배열을 탐색하기 시작합니다. 모든 반복과 array [i]의 각 값에 대해 sum과 함께 추가하고이를 합계에 저장하여 다음에 반복 할 때 sum의 초기화 된 값이 아닌 합계 값을 얻습니다. 0. 따라서 매 반복마다 합계로 저장된 일부 값이 있습니다.

반복되는 요소를 제공하는 공식을 만들거나 시리즈에 포함 된 추가 요소를 반환한다고 말할 수 있습니다. 연속적으로 1에서 5까지 주어진 시리즈가 있다고 가정합니다. 모든 숫자를 더하면 모든 숫자의 합이 주어지고 시리즈에서 반복되는 요소가 없습니다. 그리고 우리는 우리의 합 공식 인 sum – (n * (n-1)) / 2의 차이를 반환합니다.

예를 들어 보겠습니다.

arr = [2,3,4,5,2,1], 합계 = 0

0부터 시작하여 각 요소를 방문하는 전체 루프를 순회 할 수 있습니다. –>

i = 0;

sum = sum + arr [i] => sum = 2

i = 1;

sum = sum + arr [i] => sum = 5

i = 2;

sum = sum + arr [i] => sum = 9

i = 3;

sum = sum + arr [i] => sum = 14

i = 4;

sum = sum + arr [i] => sum = 16

i = 5;

sum = sum + arr [i] => sum = 17

1- (2 * (17-6)) / 6 인 sum- (n * (n-1)) / 2를 반환합니다.

17 – 15 = 2, 이것이 우리의 필수 출력입니다.

 

1에서 N-1 사이의 유일한 반복 요소 찾기

1에서 N-1 사이의 유일한 반복 요소를 찾기위한 구현

C ++ 프로그램

#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에서 N-1 사이의 유일한 반복 요소 찾기를위한 복잡도 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

O (1) 여기에 보조 공간을 사용하지 않기 때문입니다.

참조

균열 시스템 설계 인터뷰
Translate »