자기를 제외한 배열의 곱

난이도 쉽게
자주 묻는 질문 수행자 아마존 드 쇼 모건 스탠리 (Morgan Stanley) 운영
배열 수학조회수 67

문제 정책

"자체를 제외한 배열의 제품"문제는 배열에 []가 주어 졌음을 나타냅니다. 다른 인쇄 정렬 배열 p의 i 번째 인덱스에있는 값이 배열 a의 i 번째 인덱스에있는 요소를 제외하고 원래 배열의 모든 요소의 곱과 같은 크기의 p [].

자기를 제외한 배열의 곱

a [ ] = {1, 2, 3}
{6, 3, 2}

설명 : 배열 크기가 3이므로 2 번째와 3 번째 요소를 곱하면 곱은 6입니다. 마찬가지로 2 번째 및 3 번째 인덱스 요소에 대해서도이 작업을 수행합니다. 따라서 출력은 {6, 3, 2}입니다.

a [ ] = {4, 6, 1, 2}
{12, 8, 48, 24}

나누기 방법 사용

이 방법은 모든 배열 요소가 항상 0보다 큰 경우에만 효과적입니다.

암호알고리즘

1. Initialize an array a[] of size n.
2. Initialize a variable prod and store product of all the elements of the array a[] in it.
3. Create another array p[] to store products of all elements except self.
4. Traverse through array a[] and update the value of array p[] such that p[i] is equal to the division of a[i] and prod.
5. Print the array p[].

변수를 사용하여 모든 숫자의 곱 (배열의 요소, 입력)을 저장하면 문제를 해결할 수 있습니다. 그러면 현재 요소를 총 곱셈 (즉, 모든 요소의 곱)에서 나누면 각 요소에 대한 답을 찾을 수 있습니다.

암호

self를 제외한 배열의 제품에 대한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

void prodArray(int a[], int n){
    int p[n], prod=1;
    
    //Find product of all elements of a[]
    for(int i=0; i<n; i++){
        prod = prod * a[i];
    }
    
    //Create array p[] to store
    //product except self
    for(int i=0; i<n; i++){
        p[i] = prod / a[i];
    }
    
    for(int i=0; i<n; i++){
        cout<<p[i]<<" ";
    }
}

int main() {
  int a[] = {4, 6, 1, 2};
  int n = sizeof(a)/sizeof(a[0]);
  prodArray(a,n);
  return 0;
}
12 8 48 24

자체를 제외한 배열의 제품에 대한 Java 프로그램

class product{
    
    void prodArray(int a[], int n){
        int p[] = new int[n], prod=1;
        
        //Find product of all elements of a[]
        for(int i=0; i<n; i++){
            prod = prod * a[i];
        }
        
        //Create array p[] to store
        //product except self
        for(int i=0; i<n; i++){
            p[i] = prod / a[i];
        }
        
        for(int i=0; i<n; i++){
            System.out.print(p[i] + " ");
        }
    }
    
    public static void main(String[] args){
        product pro = new product();
    	int a[] = {4, 6, 1, 2};
    	int n = a.length;
    	pro.prodArray(a,n);
    }
}
12 8 48 24

복잡성 분석

시간 복잡성

의 위에), 여기서 요소의 수는 N입니다. 여기서는 먼저 알고리즘이 O (N) 시간에 실행되도록 배열을 통과했기 때문입니다.

공간 복잡성

O (1), 우리는 일정한 추가 공간을 사용했기 때문입니다. 그러나 입력을 저장했기 때문에 프로그램 전체는 O (N) 공간을 차지합니다.

나누기 방법없이

자기 문제를 제외한 배열의 Product 알고리즘

1. Initialize an array a[] of size n and a variable prod as 1.
2. Create another array p[] of the same size with all the elements as 1.
3. Traverse all the values from starting index to last index and update the values of array p[] such that p[i] = prod and prod = prod * a[i].
4. Initialize prod as 1 again and start traversing the array from last index to starting index.
5. Update array p[] such that p[i] = prod and prod = prod * a[i].
6. Print the array p[].

암호

self를 제외한 배열의 제품에 대한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

void prodArray(int a[], int n){
        
    if(n == 1) { 
        cout<<"0"; 
        return; 
    } 

    int prod = 1; 
    int p[n]; 

    /* Initialize the product array p[] as 1 */
    for(int j=0; j<n; j++) 
        p[j] = 1; 

    /* prod variable contains product of 
       elements on left side excluding a[i] */
    for(int i=0; i<n; i++) { 
        p[i] = prod; 
        prod *= a[i]; 
    } 

    /* Initialize prod to 1 for product on right side */
    prod = 1; 

    /* prod variable contains product of 
       elements on right side excluding a[i] */
    for(int i=n-1; i>=0; i--) { 
        p[i] *= prod; 
        prod *= a[i]; 
    } 
    for(int i=0; i<n; i++) 
        cout<<p[i]<<" ";

    return; 
}

int main() {
  int a[] = {4, 6, 1, 2};
  int n = sizeof(a)/sizeof(a[0]);
  prodArray(a,n);
  return 0;
}
12 8 48 24

자체를 제외한 배열의 제품에 대한 Java 프로그램

class product{
    
    void prodArray(int a[], int n){
        
        if(n == 1) { 
            System.out.print("0"); 
            return; 
        } 
  
        int prod = 1; 
        int p[] = new int[n]; 
  
        /* Initialize the product array p[] as 1 */
        for(int j=0; j<n; j++) 
            p[j] = 1; 
  
        /* prod variable contains product of 
           elements on left side excluding a[i] */
        for(int i=0; i<n; i++) { 
            p[i] = prod; 
            prod *= a[i]; 
        } 
  
        /* Initialize prod to 1 for product on right side */
        prod = 1; 
  
        /* prod variable contains product of 
           elements on right side excluding a[i] */
        for(int i=n-1; i>=0; i--) { 
            p[i] *= prod; 
            prod *= a[i]; 
        } 
        for(int i=0; i<n; i++) 
            System.out.print(p[i] + " ");
  
        return; 
    }
    
    public static void main(String[] args){
        product pro = new product();
    	int a[] = {4, 6, 1, 2};
    	int n = a.length;
    	pro.prodArray(a,n);
    }
}
12 8 48 24

복잡성 분석

시간 복잡성

의 위에), 여기서 우리는 크기가 N 인 배열을 순회했기 때문입니다.

공간 복잡성

O (1), 초기 배열 만 변경하고 추가 상수 공간 만 사용했기 때문입니다. 프로그램 전체는 O (N) 공간을 차지하지만 알고리즘 자체는 O (1) 공간 만 차지합니다.

Translate »