Pls help me with this code can't understand the error

#include <stdio.h>
#include <stdlib.h>
int main(void) {
	int T , N  , i , j , m , mul ,k, count = 0 ;
	scanf("%d" , &T);
	while(T--){
	    scanf("%d"  ,  &N);
	    int *p;
	    p = (int *)malloc(N * sizeof(int));
	    for(k = 0 ; k < N ; k++){
	        scanf("%d" , &p[k]);
	    }
	    for(i = 0 ; i < N - 1 ; i++){
	        for(j = i+1 ; j<N ; j++){
	            mul = p[i] * p[j];
	        }
	        for(m = 0 ; m < N ; m++){
	            if(mul == p[m]){
	               count += 1 ;
	               mul = 0 ; 
	            }
	        }
	    }
	    if(count > 0){
	        printf("yes\n");
	    }
	    else if(count == 0 ){
	        printf("no\n");
	    }
	}
	return 0;
}

problem code is ICPC16B

pls tell me why the last input in the example input is showing yes though it should show a no
Help would be really appreciated :slight_smile:

You’re not resetting count between testcases.

2 Likes

I set count = 0 after the while statement now the last one shows no but the problem now I am getting wrong answer when I submit :cry: :cry:

set count = 0 after the while statement now the last one shows no but the problem now I am getting wrong answer when I submit :cry: :cry:

try chaning this to

for(m = 0; m < N; m++) {
    if(mul == p[m]) {
        count++;
        break;
    }
}

There are a lot more bugs in your code. Some of them:

This shall be changed to:

for(i = 0; i < N - 1; i++) {
    for(j = i + 1; j < N; j++) {
        mul = p[i] * p[j];
        bool flag = false;
        for(m = 0; m < N; m++) {
            if(mul == p[m]) {
                flag = true;
                break;
            }
        }
        if(flag) {
           count++;
        }
    }
}
if(count == (N * (N -  1)) / 2) {
    cout << "YES" << '\n';
}
else {
    cout << "NO" << '\n';
} 
1 Like

can u pls explain why are we doing this with the count ??
if(count == (N * (N - 1)) / 2)
:grinning_face_with_smiling_eyes: :grinning_face_with_smiling_eyes:

The question:

An array a is called beautiful if for every pair of numbers a_i, a_j where (i \ne j), there exists an a_k such that a_k = a_i \times a_j. Note that k can be equal to i or j too.

Find out whether the given array a is beautiful or not!

Since you are trying to solve this problem Naively, you are trying to check for every possible pair, whether there exists any a_k as mentioned in the problem statement.

Note that there are exactly N\times (N - 1) pairs of indices (i, j),\ i\ne j. You are checking for all such possible pairs, using the below two for loops.

But we are cheating here. We aren’t checking for all pairs of (i, j) where i\ne j; instead, we are checking for all pairs of (i, j) where i\lt j. Hence the number of pairs we are checking reduces a bit.

Using the condition i \lt j, the number of pairs reduces to \cfrac{N\times (N - 1)}{2}

Therefore, we have to check if(count == (N * (N - 1)) / 2) and accordingly print the required output.

Note: The time complexity of your code is O(N^3). We can reduce it to O(N^2) using hashing and O(N\times \sqrt{A_{max}}) using factorisation. There can be a better approach of time complexity O(N\log{A_{max}}) but I cannot think of it as of now.

PS: The value \cfrac{N\times (N-1)}{2} can exceed the limits of Integer.

Edit: The problem is Ad-hoc :grimacing:. It can be solved in O(N), with a bit of case work.