The problem of “Beautiful Arrays” with C Source code

T

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

Input

First line of the input contains an integer T denoting the number of test cases. T test cases follow. First line of each test case contains an integer n denoting number of elements in a. Next line contains n space separated integers denoting the array a.

Output

For each test case, output a single line containing “yes” or “no” (without quotes) corresponding to the answer of the problem.

Approach 1: Naive

#define _CRT_SECURE_NO_WARNINGS
 
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
 
int main()
{
	uint32_t t,i,j,k, num_tests, A_size;
	int32_t  A_k, *A;
	uint8_t result;
 
	scanf("%d", &num_tests);
 
	for (t = 0; t < num_tests; t++)
	{
		scanf("%d", &A_size);
 
		result = 0;
		
		A = (int32_t *)malloc(A_size * sizeof(int32_t));
 
		for (i = 0; i < A_size; i++)
			scanf("%d", &A[i]);
		
		for (i = 0; i < A_size-1 && result==0; i++)
			for (j = i + 1; j < A_size && result == 0; j++)
			{
				A_k = A[i] * A[j];
				result = 1;
				for (k = 0; k < A_size; k++)
					if (A_k == A[k])
					{
						result =0;
						break;
					}		
			}
 
		if (result == 0)
			printf("yes\n");
		else
			printf("no\n");
 
		free(A);
	}
 
	return 0;
}

Approach 2: Advanced

#define _CRT_SECURE_NO_WARNINGS
 
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
 
int main()
{
	uint64_t t,i,k, num_tests, A_size,pos_ones,neg_ones;
	int64_t  A;
  
	scanf("%lld", &num_tests);
 
	for (t = 0; t < num_tests; t++)
	{
		scanf("%lld", &A_size);
 
		k = neg_ones = pos_ones = 0;
 
		for (i = 0; i < A_size; i++)
		{
			scanf("%lld", &A);
 
			k = A < -1 || A > 1 ? k + 1 : k;
 
			pos_ones = A == 1 ? pos_ones + 1 : pos_ones;
 
			neg_ones = A == -1 ? neg_ones + 1 : neg_ones;
 
		}
 
		if (k > 1 || (neg_ones >= 1 && k >=1) || (neg_ones >1 && pos_ones == 0))
			printf("no\n");
		else
			printf("yes\n");
	}
 
	return 0;
}

Results

Github Repository: https://github.com/devcoons/beautiful-arrays-problem

Problem found at : https://www.codechef.com/problems/ICPC16B

Disclaimer: The present content may not be used for training artificial intelligence or machine learning algorithms. All other uses, including search, entertainment, and commercial use, are permitted.

Categories

Tags