Блог пользователя my_name_is_khan

Автор my_name_is_khan, 5 лет назад, По-английски

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;
	}
}
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Constraint for Ai? For this problem it was 100 so you can brute easily.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Don't loop through all N, just loop through the ones in range from 1 to 100 (since there will be duplicates).

Also, do not use Arrays.sort, because it can be slow. Instead use Collections.sort on an array that is composed of the wrapper class (ex. Int instead of int).

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Value of 1<=A[i]<=100, so you can easily create a frequency array of size 100 and then count all the numbers. Then you can check the triplets in bruteforce also as it will not take more than O[1000000] time. if you get any help by my comment please upvote it.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Yes, Dont loop through all N because it contains duplicates. Just Loop through 1 to 100. It reduces time complexity