Short C++ solution - O(n) time - O(n) space

google
programming
interview-questions
Tags: #<Tag:0x00007f18227ea298> #<Tag:0x00007f18227ea068> #<Tag:0x00007f18227e9ed8>

#1

Using some maths, and the knowlede that kth row of Pascal’s traingle is basically kCr, r ranging from 0 to k:

vector Solution::getRow(int A) {
vector result;
long long int nume=1,deno=1;
int top=A+1,bottom=0;
result.push_back(1);
if(A==1)
{
result.push_back(1); //1st row is 1 1 according to the test case here, not just 1. May be a mistake.
return result;
}
//Since factorials can be large, used a different way of generating nCr without doing the whoel factorials, multiplying only as much as is needed
//The maths is just for counting differently in terms on even and odd. Dont sweat too much over it, you can probably formulate it easier
for(int i=1;i<=(A+1)/2-(A%2==0?0:1);i++)
{
nume*=(top-1);
deno*=(bottom+1);
result.push_back(nume/deno);
top–;bottom++;
}
int size=result.size()-1;
//Mirroring the other half now, taking care of even and odd cases
for(int i=(size-(A%2==0?1:0));i>=0;i–)
result.push_back(result[i]);
return result;
}


#2

you forgot that you are multiplying (n-r) times in nume and r times in deno for every r. i e. you are multiplying (n - r + r) times = n times for every r. even when you are not dealing with whole factorial. so it is not O(n) its O(n^2). it is equivalent to keeping two arrays and doing sum iteratively over them.