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

[raider_9]

#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

[ssjgz]

You’re not resetting count between testcases.

In which type of case is the code failing?

Consider the test input: 3 1 11 6 4 9 9 8 1 6 2 10 10 5 and also consider not declaring (and initialising) all your variables at the top of main but only at the last possible point before you can use them! This eliminates the class of error that you’re making here. Of all the anti-patterns I see in CP code, this is one of the strangest. See e.g. this. There’s another recent example here - are there some ancient professors teaching students to do this?

[raider_9]

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

[raider_9]

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

[suman_18733097]

@raider_9

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

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:

@raider_9

        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 ; 
	            }
	        }
	    }

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';
} 

[raider_9]

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

[suman_18733097]

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.

@suman_18733097

for(i = 0; i < N - 1; i++) {
    for(j = i + 1; j < N; j++)

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 . It can be solved in O(N), with a bit of case work.