CODEWITHSUNDEEP
c++optimization
Mr. GT
Mr. GT

Reputation: 13

Reduce run-time in C++

Recently, CodeVita Season 9 is running all over the world which is organized by TCS. There's one problem statement given below.

Problem Description :

Given an array of integers A, and an integer K find number of happy elements.

Element X is happy if there exists at least 1 element whose difference is less than K i.e. an element X is happy, if there is another element in the range [X-K, X+K] other than X itself.

Constraints

1 <= N <= 10^5

0 <= K <= 10^5

0 <= A[i] <= 10^9

Time Limit

1

According to this, I've done my code with C++. Here's the code,

#include<iostream>
#include<math.h>
using namespace std;
int main(){
    int siz, x;
    cin>>siz;
    cin>>x;
    if(siz>= 1 && siz<= pow(10, 5) && x>=0 && x<= pow(10, 5)){
        int a[siz];
        for(int i=0; i<siz; i++){
            cin>>a[i];
            if(a[i]>=0 && a[i]<= pow(10, 9))
                continue;
            else
                break;
        }
        int cnt, op = 0, i = 0;
        while(i<siz){
            cnt = 0;
            int dif1 = a[i] - x;
            int dif2 = a[i] + x;
            for(int j=0; j<siz; j++){
                if(a[j]>= dif1 && a[j] <= dif2){
                    if(a[j] != a[i])
                        cnt=1;
                }
            }
            if(cnt == 1)
                ++op;
            i++;
        }
        cout<<op;
    }
    return 0;
}

It shows the same output as wanted but on CodeVita Plateform, they're not accepting this code showing "Time Limit Exceeds". Now, I don't know how to make this code the way it doesn't exceeds the time limit. Seeking support from community.

Upvotes: 0

Views: 188

Answers (1)

Ben
Ben

Reputation: 159

you could take advantage of very efficient tools of standard library. If you store your value in a std::vector, you can use the std::sort to have the values sorted. Then iterate on the vector looking the difference between two consecutive elements.

It will be more efficient because standard library algorythms are efficient. Sorting may be as low as O(n log n) on average, and final search is O(n)

Your searching loop is O(n2), which is much worse.

Upvotes: 1

Related Questions