(CHFQUEUE DSA) what's wrong with this logic?

CodeChef-DSA-learners
, ,
1

find question here: CodeChef: Practical coding for everyone

code:
#include
using namespace std;

#define int long long

int32_t main() {
// your code goes here
int n,k,i,product=1,j,temp=0;
cin>>n>>k;
int p[n];

for(i=0;i<n;i++)
{
    cin>>p[i];
}


for(j=0;j<n-1;j++)
{
    i=j+1;
    for(i;i<n;i++)
    {
        if(p[j] > p[i])
        {
            temp = ((i - j) + 1);
            product*=(temp) % 1000000007;
            //cout<<"pro"<<product<<" ";
            break;
        }
    }
}

// product = product % 1000000007;
cout<<product<<endl;

return 0;

}

2

The time complexity of your code is O(n^2). Whereas the time limit given is 1 sec. Try to optimize your code.

1 Like
3

yes!done

1 Like
4

Can you tell me the stack approach you used?
I did not exactly get where you initialized stack.

5

this is whai i did,
consider s as stack and product as final answer

for(i=0;i<n;i++)
{
while(!s.empty() && p[i] < p[s.top()])
{
temp = s.top();
temp = i - temp + 1;
product = ((product * temp) % M);
s.pop();
}
s.push(i);
}

2 Likes
6

Cool! Thanks.

1 Like
7

Its cool. perfact answer.

1 Like