How can I solve this problem in the given link without using nested loop???

hackerrank problem

http://hr.gs/4ottg 

Its showing time out with nested loop

Proma
Proma Roy
Proma

Please Log in to answer

Note: Your answer should not be too short. Please wait a few seconds for the editor to load



Please make sure the answer is not too short

1 Answer

preda2or
preda2or 09:50, Oct 11
Shubham Kumar Gupta

The constraints in this problem are such that it can be solved using 2 nested loops. Optimization is not required.
For each i from from [0 , N - 1] we run a loop  j from [i + 1,  N - 1]  and check the divisibility of each pair (i, j) and increase the count accordingly.
Code : (C++)

    int n, k;
    cin >> n  >> k;
    int arr[n];
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if ((arr[i] + arr[j]) % k == 0) {
                cnt++;
            }
        }
    }
    cout << cnt;

Complexity : O ( n * n)
 




Please make sure the answer is not too short
0 Upvotes
Comments
No Comments yet