Help me out in finding out my error

#1

can anyone tell me why #include <bits/stdc++.h>
using namespace std;
bool check(int i,int *ar,int n)
{
if(i<1 &&i>n)
{
return false;
}
else
{
if(ar[i]!=0)
{
bool a=check(i+ar[i],ar,n);
if(a)
{
return true;
}
bool b=check(i-ar[i],ar,n);
return a||b;
}
else{
return true;
}
}
}
int main(){
int n,sv;
cin>>n>>sv;
int ar[n];
for(int i=1;i<=n;i++)
{
cin>>ar[i];
}
int i=sv;
bool ans=check(sv,ar,n);
if(ans==true)
{

	cout<<"YES";
}
else
{
	cout<<"NO";
}

}it is not paasing all the test cases?

#2

anyone is there please reply ?

#3

Please share the link of Code

How to Share Link of Code??

  1. paste your code at https://ide.codingblocks.com/

  2. click->file->save

  3. after a link will be generated at top in place of url something like: https://ide.codingblocks.com/s/12345

  4. share this link

#4


have a look

#5

bro are u looking

#6

for the input
5 3
1 1 1 1 1
your code is giving run time error

if(i<1 && i>n)
{
return false;
}
and also
in this condition there should be OR(||)
otherwise both condition can never be true at same time

and also this approach will not work for bigger value of n
look at constraints of question

#7

bro my code complexity is 2 to power n right ?but it should run fine for lower value of n

#8

my code complexity is 2 to power n;
right but it should work in lower value of n

#9

yes time complexity is 2^n and which is too high for
1 <= A.length <= 5 * 10^4

also code is not running for some case like i mention when all ones

#10

it can be solved in o(n^2) by recursive memoisation (dp) beacuse we can store the value at certain beacuse when you draw tree by recursion you will get to know that there is overlapping problem…

#11

yes absolutely correct you have to do so

like this

#12

thks a lot brother for helping me

#13

bro why there is use to track the node is visited and also you are returning false if it islalready visited ?

#15

#include <bits/stdc++.h>
using namespace std;
int dp[100000];
bool *visited;
bool check(int i,int *ar,int n)
{
if(i<1 || i>n)
{
return false;
}

	if(dp[i]!=-1)
	{
		return dp[i];
	}
	
	if(ar[i]==0)
	{
		return true;
	}
    
    if(visited[i])return false;
	visited[i] = 1;
    bool a=check(i+ar[i],ar,n);
    if(a)
    {
        return dp[i]=true;
    }
    bool b=check(i-ar[i],ar,n);
    return dp[i]=b;

}
int main(){
int n,sv;
cin>>n>>sv;
int ar[n];

for(int i=1;i<=n;i++)
{
    cin>>ar[i];
    
}

for(int i=1;i<=n;i++)
{
    dp[i]=-1;
    
}
visited=new bool[100000]{0};
int i=sv;
bool ans=check(sv,ar,n);
if(ans)
{
	

	cout<<"YES";
}
else
{
	cout<<"NO";
}

}
this code is not passing

#16

sometime you may stuck in cycle and keep moving to and fro
this is done to avoid this

#17

instead of pasting code directly here you can paste it at

  1. paste your code at https://ide.codingblocks.com/
  2. click->file->save
  3. after a link will be generated at top in place of url something like: https://ide.codingblocks.com/s/12345
  4. share this link