### Thread: Adobe codesprint challenge

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
2
Rep Power
0

#### Adobe codesprint challenge

I recently attempted GAME problem on Interviewstreet.
Problem:
Player A and B , agree to play several games.

Game rules:-

1. A game never ends in a draw.

2. Player "A" starts first in the first game.

3. Player who starts a game has probability "P" of winning that game.

4. The one who loses starts the new game.

Everyone knows no one settles after losing a game. One more game please!!, is the word of mouth whenever someone loses. This way people end up playing many games.

Now A wants to know the probability that he will win the Nth game.

Input:
First line - probability P.
Second line - Q ( Number of query ).
Next Q lines, each have an integer N.

Output:
For each query output the probability that A will win Nth game.
Output the answer rounded to 4 decimal places. While rounding to 4 decimal place 0.12345 becomes 0.1235, 0.43531 becomes 0.4353 and 0.32768 becomes 0.3277.

Constraint :-

0.0 <= P <= 1.0
0 < Q <= 200000
0 < N <= 1000000

Sample Input:-
0.2
3
1
4
7
Sample Output:-
0.2000
0.4352
0.4860

My solution is as follows:
#include <iostream>
using namespace std;

double arr[1000000]={0};
double find(double p,long long int n)
{
double ans=0.0;double q=0.0;
if(n==1)
{
arr[1]=p;
return p;
}

if(arr[n-1]!=0)
{
return ((1-p)*(arr[n-1])+p*(1-arr[n-1]));
}
else
{
q=find(p,n-1);
ans=(1-p)*q+p*(1-q);
arr[n]=ans;
return ans;
}
}
int main()
{
double p=0;int q=0;long long int n=0;double ans=0.0;long long int i=0;
scanf("%lf",&p);
scanf("%d",&q);
while(q--)
{
scanf("%lld",&n);
ans=find(p,n);

printf("%.4lf\n",ans);
}

return 0;
}

It passed 10/11 test-cases and for one test case it gives me Segmentation fault(core dumped). I did a lot of research (googling) but could not understand why this error comes up. My logic is correct I think since it passed 10 test-cases. I would be highly obliged if anyone could tell me why it failed?

Thanks in advance.
2. First, use [code][/code] tags when posting code, so it looks nice and readable.
Code:
```#include <iostream>
#include <cstdio>
using namespace std;

double arr[1000000] = { 0 };

double find(double p, long long int n)
{
double ans = 0.0;
double q = 0.0;
if (n == 1) {
arr[1] = p;
return p;
}

if (arr[n - 1] != 0) {
return ((1 - p) * (arr[n - 1]) + p * (1 - arr[n - 1]));
} else {
q = find(p, n - 1);
ans = (1 - p) * q + p * (1 - q);
arr[n] = ans;
return ans;
}
}

int main()
{
double p = 0;
int q = 0;
long long int n = 0;
double ans = 0.0;
long long int i = 0;
scanf("%lf", &p);
scanf("%d", &q);
while (q--) {
scanf("%lld", &n);
ans = find(p, n);

printf("%.4lf\n", ans);
}

return 0;
}```
Second, decide which language you're programming in.
The first couple of lines are C++, but the rest of it is pure C.

> It passed 10/11 test-cases and for one test case it gives me Segmentation fault(core dumped).
Well I tried your 3 test cases, got your output, and it didn't crash.
If you want us to say anything else, you need to tell us what your other test cases are, especially the one which caused a crash.
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
2
Rep Power
0
Originally Posted by salem
First, use [code][/code] tags when posting code, so it looks nice and readable.
Code:
```#include <iostream>
#include <cstdio>
using namespace std;

double arr[1000000] = { 0 };

double find(double p, long long int n)
{
double ans = 0.0;
double q = 0.0;
if (n == 1) {
arr[1] = p;
return p;
}

if (arr[n - 1] != 0) {
return ((1 - p) * (arr[n - 1]) + p * (1 - arr[n - 1]));
} else {
q = find(p, n - 1);
ans = (1 - p) * q + p * (1 - q);
arr[n] = ans;
return ans;
}
}

int main()
{
double p = 0;
int q = 0;
long long int n = 0;
double ans = 0.0;
long long int i = 0;
scanf("%lf", &p);
scanf("%d", &q);
while (q--) {
scanf("%lld", &n);
ans = find(p, n);

printf("%.4lf\n", ans);
}

return 0;
}```
Second, decide which language you're programming in.
The first couple of lines are C++, but the rest of it is pure C.

> It passed 10/11 test-cases and for one test case it gives me Segmentation fault(core dumped).
Well I tried your 3 test cases, got your output, and it didn't crash.
If you want us to say anything else, you need to tell us what your other test cases are, especially the one which caused a crash.

Ok so when I give input as 1000000 for N then it crashes.
4. Two things are problematic.

> q = find(p, n - 1);
1000000 recursive calls will eat a hell of a lot of stack space.
With those parameters and local variables, you could be looking at 30+ bytes per stack frame.

Most machines limit stack space to between 1 and 8MB, so you're comfortably blowing that away.

> arr[n] = ans;
On the first iteration, this is an out of bound memory access when n = 1000000