Dado um array A consistindo em N inteiros positivos.
Encontre o menor número inteiro positivo, d, st, não existe nenhum par de inteiros (i,j)(1<=i<j<= N) onde abs(A_i - A_j) é divisível por d.
Dados N elementos, e assumindo todos únicos, o número de diferenças pode ser:
Nº - 1º, Nº - 2º, ..., Nº - (N-1)º;
(N-1)º - 1º, (N-1)º - 2º, ..., (N-1)º - (N-2)º;
(N-2)º - 1º, (N-2)º - 2º, (N-2)º - 3º, ..., (N-2)º - (N-3)º;
.
.
.
2º - 1º;
ou seja, um total de N(N-1)/2 diferenças.
Deixe o array de inteiros ser chamado: arr. Então, tenha:
int arr[N];
Não tenho ideia de como resolver esse problema de uma maneira melhor do que a força bruta, na qual definitivamente existe O (N ^ 2) complexidade de tempo.
Mas parece que uma maneira mais fácil é calcular o mdc de dois números, digamos, tomando o menor número inteiro
d = arr[0]
Então, é possível calcular recursivamente o
mdc(d, arr[i]), i=1,2,3,..., N-1.
Mas não consigo descobrir se está correto.
`
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int checked_atoi (const char *from) {
char *endptr= NULL;
long lval= strtol(from, &endptr, 10);
if (*endptr) {
fprintf(stderr, "invalid number '%s'\n", from);
exit(12);
}
else if (lval<INT_MIN || lval>INT_MAX) {
fprintf(stderr, "value '%ld' out of range\n", lval);
exit(13);
}
return (int)lval;
}
int gcd(int a, int b, int c){
if (b==0)
return a;
printf("\n step: %d<> gcd : a: %d, b: %d", c++, a, b);
return gcd(b, a%b, c);
}
int find_smallest_d(int *arr, int N){
int smallest_d = arr[0];
printf("\n find_smallest_d");
for (int i=1; i<N; i++){
smallest_d = gcd(smallest_d, arr[i], 1);
}
return smallest_d;
}
int main(int argc, char *argv[]){
int N=argc-1;
printf("The size of array: %d", N);
int arr[N];
for (int i=0; i<N; ++i) {
arr[i]= checked_atoi(argv[i+1]);
}
printf("The %d values:", N);
for (int i=0; i<N; ++i) {
printf(" %d", arr[i]);
}
printf("\n");
int smallest_d = find_smallest_d(arr, N);
printf("\n smallest value of d is: %d", smallest_d);
}
`
O resultado obtido sugere que a implementação da lógica no programa pode estar errada, como obter entradas de: 12, 23, 34, 45, 56, 67; resposta de 1. O valor único das diferenças abs(arr[i]-arr[j]) são:
`
1. abs(12-23) = 11,
2. abs(12-34) = 22,
3. abs(12-45) = 33,
4. abs(12-56) = 44,
5. abs(12-67) = 55,
`
Portanto, o mdc deveria ser 11; embora não esteja claro se o GCD é necessário ou não.
Além disso, a resposta deve ser: 10.