특별 번호

난이도 쉽게
자주 묻는 질문 JIO MAQ o9 솔루션 TCS
숫자 자리 학교 프로그래밍조회수 112

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

숫자에 대해 무엇이 그렇게 특별 할 수 있습니까?

우리가 알아 보자.

우리는 N 개의 숫자 배열을 가지고 있습니다. 숫자 자체를 제외하고 하나 이상의 숫자로 나눌 수있는 숫자는 특별 할 수 있습니다.

먼저 다른 것으로 넘어 가기 전에 몇 가지 예를 통해이 문제를 해결하겠습니다.

1,2,3 배열

특수 번호 2 및 3

이유는 무엇입니까?

2도 1로 나눌 수 있습니다.

1,2,5,9의 배열

특수 번호는 2,5 및 9입니다.

이유는 무엇입니까?

이 숫자는 1로 나눌 수 있으므로

2,3,4,6,8,9의 배열

특수 번호는 4.6.8.9입니다.

둘째,이 문제에 접근하는 방법을 살펴 보겠습니다.

특수 번호에 대한 접근 방식 1

브 루트 포스

  • 우리는 배열을 통과합니다.
  • 각 요소를 나누는 요소를 확인합니다.

특수 번호에 대한 Java 코드

// "static void main" must be defined in a public class.
public class Main 
{
    public static void diCheck(List<Integer> arr, int n) 
    { 
        Set<Integer> store = new HashSet<Integer>(); 
        for(int i=0;i<arr.size();i++)
        {
            for(int j=i+1;j<arr.size();j++)
            {
                if(arr.get(j)%arr.get(i)==0)
                    store.add(arr.get(j));
            }
        }
        for(Integer a:store)
        {
            System.out.print(a+" ");
        }
    } 
    public static void main(String[] args) 
    {
        List<Integer> arr = Arrays.asList(1, 2, 3, 8, 6, 9, 5); 
        int n = arr.size(); 
        diCheck(arr, n); 
    }
}

특수 번호에 대한 C ++ 코드

void diCheck(int arr[], int n) 
{ 
    unordered_set<int> store; 
    int maxs = -1; 
    for (int i = 0; i < n; i++) 
    { 
        for(int j=i+1;j<n;j++)
        {
            if(arr[j]%arr[i]==0)
                store.insert(arr[j]);
        }
    } 
    for (auto x : store) 
        cout << x << " "; 
} 
int main() 
{ 
    int arr[] = { 1, 2, 3, 5, 8, 6, 9, 10 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    diCheck(arr, n); 
  
    return 0; 
}

복잡성 분석

시간 복잡도 = O (n ^ 2)

어떻게?

  • 위의 접근 방식은 두 개의 루프를 사용합니다.
  • 첫째, 제수를 넘어갈 바깥 쪽
  • 둘째. 배당금을 넘을 내부 하나
  • 이것은 시간 복잡도를 O (n ^ 2)로 가져옵니다.

공간 복잡성 = O (1)

어떻게?

변수 만 사용하므로 공간이 많이 필요하지 않습니다.

특수 번호에 대한 접근 방식 2

해시 테이블 사용

첫째, 우리는 접근 작은 입 크기의 입맛에 맞는 조각으로.

  • 먼저 모든 요소를 ​​정렬합니다.
  • 변수를 사용하여 최대 요소 찾기
  • 최대 요소가 필요하십니까?
  • 해당 숫자까지 사용 가능한 제수를 찾는 데 사용하려면
  • num * 2부터 시작합니다
  • 배수를 얻기 위해 그 자체에 숫자를 더합니다.
  • 멀티플을 얻을 때마다 세트에 저장합니다.
  • 우리가 얻은 숫자가 중복되지 않도록 숫자를 집합에 저장합니다.
  • 제수가 있으면 숫자는 특별합니다.
  • 따라서 특수 번호가 추가됩니다.

둘째, 전체 프로세스를 실행할 작은 이미지를 얻습니다. 이렇게하면 문제를 파악할 수없는 모든 사람이 문제를 완전히 이해할 수 있습니다.

특별 번호
특별 번호 설명

여기의 빨간색 부분은 번호가 이미지도에 추가되었음을 나타냅니다.

자바 코드

// "static void main" must be defined in a public class.
public class Main 
{
    public static void diCheck(List<Integer> arr, int n) 
    { 
        List<Integer> store = new ArrayList<Integer>(); 
        int max = Integer.MIN_VALUE; 
        for (int i = 0; i < n; i++) 
        { 
            store.add(arr.get(i)); 
            max = Math.max(max,arr.get(i)); 
        }
        LinkedHashSet<Integer>ans=new LinkedHashSet<Integer>();
        for(int i=0;i<n;i++)
        {
            if(arr.get(i)!=0)
            {
                for(int j=arr.get(i)*2;j<max;j++)
                {
                    if(store.contains(j))
                        ans.add(j);
                }
            }
        }
        List<Integer>ret=new ArrayList<Integer>(ans);
        for(int i=0;i<ret.size();i++)
            System.out.print(ret.get(i)+" ");
    } 
    public static void main(String[] args) 
    {
        List<Integer> arr = Arrays.asList(1, 2, 3, 8, 6, 9, 5); 
        int n = arr.size(); 
        diCheck(arr, n); 
    }
}

C ++ 코드

void diCheck(int arr[], int n) 
{ 
    unordered_set<int> store; 
    int maxs = -1; 
    for (int i = 0; i < n; i++) 
    { 
        store.insert(arr[i]); 
        //Finding the max element 
        maxs= max(maxs, arr[i]); 
    } 
  
    // Traversing the array elements and storing the multiples
    unordered_set<int> res; 
    for (int i = 0; i < n; i++) 
    { 
        if (arr[i] != 0) 
        { 
            for (int j = arr[i] * 2; j <= maxs; j++)
            { 
                if (store.find(j) != store.end()) 
                    res.insert(j); 
            } 
        } 
    } 
    unordered_map<int, int> map; 
    for(int i = 0; i < n; i++) 
        map[arr[i]]=map[arr[i]]+1; 
  
    unordered_map<int, int>::iterator it; 
    vector<int> ans; 
    for (it = map.begin(); it != map.end(); it++) 
    { 
        if (it->second >= 2) 
        { 
            if (res.find(it->first) == res.end()) 
            { 
                int val = it->second; 
                while (val--) 
                    ans.push_back(it->first); 
            } 
        } 
  
        // If frequency is greater than 1 and is divisible by any other number 
        if (res.find(it->first) != res.end()) 
        { 
            int val = it->second; 
            while (val--) 
                ans.push_back(it->first); 
        } 
    }
    //Printing special numbers
    for (auto x : ans) 
        cout << x << " "; 
} 
int main() 
{ 
    int arr[] = { 1, 2, 3, 5, 8, 6, 9, 10 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    diCheck(arr, n); 
  
    return 0; 
}
1, 2, 3, 5, 8, 6, 9, 10
2,3,5,8,9,10

참고 : 위의 접근 방식은 작은 숫자에만 적합합니다.

특수 번호에 대한 복잡성 분석

시간 복잡도 = O (n ^ 2)

  • 접근 방식의 시간 복잡도는 O (n ^ 2)입니다.
  • 정렬에는 O (n log n) 시간이 걸립니다.
  • 외부 루프를 살펴보고 해시에서 숫자를 선택합니다.
  • 내부 루프에서 제수를 찾아서 세트에 추가합니다.
  • 결국 시간 복잡도를 O (nlogn) + O (n ^ 2)로 합산
  • n ^ 2> n logn으로
  • 시간 복잡도는 O (n ^ 2)가됩니다.

공간 복잡성 = O (n)

  • 우리는 요소를 추적하기 위해 해시와 세트를 사용합니다.
  • n 크기의 배열 / ArrayList / 벡터가 제공됩니다.
  • 따라서 모든 요소를 ​​저장하는 데 사용되는 공간의 합계는 O (n)입니다.

참조

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