[Daily Coding Problem] Problem #2 : Uber Interview 문제

This problem was asked by Uber.

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Follow-up: what if you can't use division?

---

1.When I first saw this question, I could only think of Brute Force.Time complexity would be O(N^2)
(처음에 봤을 때는 브루트 포스 밖에 생각하지 못했다. O(N^2))

#include<iostream>
using namespace std;

void func(int arr[],int arrsize)
{
    int*ans=new int(arrsize);
    for(int i=0;i<arrsize;i++)
        {
        int temp=1;
        for(int j=0;j<arrsize;j++)
        {
            if(j!=i)
                temp*=arr[j];
        }
        ans[i]=temp;

        } 
        
        for(int i=0;i<arrsize;i++)
        {
            cout<<ans[i]<<"\n";
        }
}

int main()
{
    int arr[]={1,2,3,4,5};
    func(arr,sizeof(arr)/sizeof(int));
    return 0;
}

2. I found another good answer in Stack Overflow. Time complexity would be O(N)
(스택오버플로우에서 좀 더 좋은 답을 찾을 수 있었습니다. O(N))

https://stackoverflow.com/questions/2680548/given-an-array-of-numbers-return-array-of-products-of-all-other-numbers-no-div

Given an array of numbers, return array of products of all other numbers (no division)

We should find an answer that the product of all the numbers in the original array except the one at i. The answer would be a[0]*a[1]*•••*a[i-1]*a[i+1]*•••*a[n-2]*a[n-1]  when the index is i. Therefore, if we have 2 numbers like <a[0]*a[1]*•••*a[i-1]> and <a[i+1]*•••*a[n-2]*a[n-1]>, we can find an answer.
(우리는 index i를 제외한 숫자들을 다 곱한 값을 찾아야하고 답은 a[0]*a[1]*•••*a[i-1]*a[i+1]*•••*a[n-2]*a[n-1]일 것이다. 따라서 a[0]*a[1]*•••*a[i-1], a[i+1]*•••*a[n-2]*a[n-1] 값을 각각 갖고 있다면 답을 낼 수 있을 것이다.)

#include<iostream>
using namespace std;

void func(int arr[],int arrsize)
{
    int* arr1=new int(arrsize);
    int* arr2=new int(arrsize);
    int temp1=1;
    int temp2=1;
    for(int i=0;i<arrsize;i++)
    {
        if(i==0)
        {
            arr1[i]=1;
            temp1*=arr[i];
            arr2[arrsize-1]=1;
            temp2*=arr[arrsize-1];
        }
        else
        {
            arr1[i]=temp1;
            temp1*=arr[i];
            arr2[arrsize-1-i]=temp2;
            temp2*=arr[arrsize-1-i];
        }
        
        } 
        
        for(int i=0;i<arrsize;i++)
        {
            cout<<arr1[i]*arr2[i]<<"\n";
        }

}
int main()
{
    int arr[]={1,2,3,4,5};
    func(arr,sizeof(arr)/sizeof(int));
    return 0;
}