I have tried to solve it for many times. But i cannot decrease complexity. Can anyone please help me ? Problem:
Given an array A of N integers. Find the number of good triplets (i, j, k), where i, j, k are all distinct indices such that 0 < i , j , k <= N. A good triplet (i, j, k) is a triplet such that the sum, S = A[i] + A[j] + A[k], is divisible by exactly one of A[i], A[j], or A[k].
Array values of a triplet (i,j,k) is (A[i], A[j], A[k]).
input: N=4 A=[1,2,2,1]
output: 12
Explanation : S=2+2+1=5 is divisible only by number 1 in the triplet and the triplet with array values 1, 1, 2 is not a good triplet as S = 4 is divisible by all three. So there are two triplets (1,2,2) and (2,2,1). Look at the i,j,k values which are indices. So, there are 12 possibilities of triplets of indices that can have array values as 2, 2, 1. They are:
(1, 2, 3), (1, 3, 2), (2, 1, 3), (3, 1, 2), (2, 3, 1), (3, 2, 1), (2, 3, 4), (2, 4, 3), (3, 2, 4), (4, 2, 3), (3, 4, 2), (4, 3, 2).
My attempt:
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int N=sc.nextInt();
int[] A=new int[N];
for(int i=0;i<N;i++){
A[i]=sc.nextInt();
}
Arrays.sort(A);
int i,j,k,count=0;
for(i=0;i<N;i++){
for(j=i+1;j<N;j++){
for(k=j+1;k<N;k++){
if(getIfGood(A[i],A[j],A[k])) count+=6;
}
}
}
System.out.println(count);
}
static boolean getIfGood(int a, int b, int c){
int count=0,sum=a+b+c;
if(sum%a==0) count++;
if(sum%b==0) count++;
if(sum%c==0) count++;
if(count==1) return true;
return false;
}
}