Sticks ---

help
,
1

PROBLEM

#include <bits/stdc++.h>
using namespace std;
int t,n,l,res;

int length,breadth;
int temp;
int main()
{
    cin>>t;
    for(int k=0;k<(t);++k){
        res=-1;
        temp=0;
        length=0;
        breadth=0;

        cin>>n;
        int lengths[n];
        for(int i =0;i<n;++i)
        {
            lengths[i]=0;
        }
        for(int i=0;i<n;++i){
            cin>>lengths[i];
        }
        sort(lengths,lengths+n);
        for(int i=n-1;i>0;--i){
            if(count(lengths,lengths+n,lengths[i])<2){
                        continue;

            }else if(temp==0){
                length=lengths[i];
                ++temp;
                int currcount = count(lengths,lengths+n,lengths[i]);
                for(int m=0;m<currcount;++m)
                {
                    --i;
                }
                ++i;


            }else if(temp==1){
                breadth=lengths[i];
                ++temp;

            }
            else if(temp==2){

                break;
            }else{
                res=-1;
            }


        }
        res=length*breadth;
        if(res==0){
            res=-1;
        }

        cout<<res<<"\n";

    }
}

I tried to debug my code and finally solved the test cases. but there is some limitation in this code i think… Anyone Help Please?

2

The Time complexity of your approach is O(N^2). The problem can be solved in O(N\log N) time.
Since N doesn’t exceed 10^3, your solution passed. Else it would have resulted in \text{TLE}.

Edit: Your code fails for the following test case.

Input

1
5
5 5 5 3 5

Expected Output

25

Your Output

-1
3

VERY INTERESTING
CORRECTED CODE:-

#include <bits/stdc++.h>
using namespace std;
int t,n,l,res;

int length,breadth;
int temp;
int main()
{
    cin>>t;
    for(int k=0;k<(t);++k){
        res=-1;
        temp=0;
        length=0;
        breadth=0;

        cin>>n;
        int lengths[n];
        for(int i =0;i<n;++i)
        {
            lengths[i]=0;
        }
        for(int i=0;i<n;++i){
            cin>>lengths[i];
        }
        sort(lengths,lengths+n);
        for(int i=n-1;i>0;--i){
            if(count(lengths,lengths+n,lengths[i])<2){
                        continue;

            }
            else if(count(lengths,lengths+n,lengths[i])>3)
            {
                length=lengths[i];
                breadth=lengths[i];
                break;
            }
            
            else if(temp==0){
                length=lengths[i];
                ++temp;
                int currcount = count(lengths,lengths+n,lengths[i]);
                for(int m=0;m<currcount;++m)
                {
                    --i;
                }
                ++i;


            }else if(temp==1){
                breadth=lengths[i];
                ++temp;

            }
            else if(temp==2){

                break;
            }else{
                res=-1;
            }


        }
        res=length*breadth;
        if(res==0){
            res=-1;
        }

        cout<<res<<"\n";

    }
}

Now what might be the LIMITATION

4

Wait how did you calculated estimated time with just O(n3)

5

Another test case:

Input

2
10
6 1 4 3 6 9 3 4 4 4 
8
3 2 7 7 3 3 3 6

Expected Output

24
21

Your Output

16
9
6

Thanks