HackerRank Java Between Two Sets
문제링크 : https://www.hackerrank.com/challenges/between-two-sets/problem
You will be given two arrays of integers and asked to determine all integers that satisfy the following two conditions:
- The elements of the first array are all factors of the integer being considered
- The integer being considered is a factor of all elements of the second array
These numbers are referred to as being between the two arrays. You must determine how many such numbers exist.
For example, given the arrays and , there are two numbers between them: and . , , and for the first value. Similarly, , and , .
Function Description
Complete the getTotalX function in the editor below. It should return the number of integers that are betwen the sets.
getTotalX has the following parameter(s):
- a: an array of integers
- b: an array of integers
Input Format
The first line contains two space-separated integers, and , the number of elements in array and the number of elements in array .
The second line contains distinct space-separated integers describing where .
The third line contains distinct space-separated integers describing where .
The second line contains distinct space-separated integers describing where .
The third line contains distinct space-separated integers describing where .
Constraints
Output Format
Print the number of integers that are considered to be between and .
Sample Input
2 3
2 4
16 32 96
Sample Output
3
Explanation
2 and 4 divide evenly into 4, 8, 12 and 16.
4, 8 and 16 divide evenly into 16, 32, 96.
4, 8 and 16 divide evenly into 16, 32, 96.
4, 8 and 16 are the only three numbers for which each element of a is a factor and each is a factor of all elements of b.
문제 요약:
배열 a, b 두 개가 주어진다.
a 배열에서는 a 원소가 제수로
b 배열에서는 b 원소가 피제수로
나누었을 때 모두 나누어 떨어지는 숫자를 구하면 된다.
접근 방법
a 배열의 최소 공배수와
b 배열의 최대 공약수를 먼저 구하고
그 사이에 있는 모든 수를 위의 조건에 맞는지 검증한다.
위의 조건에 해당되면 카운트를 세주고, 모두 검증한 후에 카운트를 리턴 해준다.
최소 공배수와 최대 공약수 사이의 값들을 모두 검증하지 않고 필터링 할 수 있을 것 같은데,,
그것 까진 생각을 못하겠다.
난이도가 Easy라고 해서 만만할 줄 알았지만, 아니였다..
처음에 lcm, gcd 모두 int 타입으로 했었다.
하지만 테스트 케이스 중에 아래와 같은 케이스가 있었다.
10 10
100 99 98 97 96 95 94 93 92 91
1 2 3 4 5 6 7 8 9 10
배열 a에서 최소 공배수가 int 타입의 값을 벗어나서 마이너스값이 나왔었다.
lcm은 겁나 커질 수 있기때문에,, long 타입으로 모두 바꿔주었다..
/*
* Complete the getTotalX function below.
*/
static int getTotalX(int[] a, int[] b) {
/*
* Write your code here.
*/
int cnt = 0;
long lcm = lcm(a);
long gcd = gcd(b);
if(lcm > gcd)
return 0;
for(long i = lcm; i <= gcd; i++){
int aCnt = 0;
for(int aa = 0; aa < a.length; aa++) {
if(i % a[aa] == 0)
aCnt++;
}
int bCnt = 0;
for(int bb = 0; bb < b.length; bb++) {
if(b[bb] % i == 0)
bCnt++;
}
if(aCnt == a.length && bCnt == b.length)
cnt++;
}
return cnt;
}
public static long gcd(int[] arr){
long result = 0;
if (arr.length > 1){
long gcd = gcd(arr[0], arr[1]);
for (int i = 2; i < arr.length; i++){
gcd = gcd(arr[i], gcd);
}
result = gcd;
} else {
result = arr[0];
}
return result;
}
public static long gcd(long a, long b) {
long number1, number2;
long remain = 1;
if(a>b){
number1 = a;
number2 = b;
}
else{
number1 = b;
number2 = a;
}
while(remain>0){ // 유클리드 호제법
remain = number1%number2;
number1 = number2;
number2 = remain;
}
return number1; //최대공약수
}
public static long lcm(int[] arr){
long result = 1;
if (arr.length > 1){
long lcm = lcm(arr[0], arr[1], gcd(arr[0], arr[1]));
for (int i = 2; i < arr.length; i++){
lcm = lcm(lcm, arr[i], gcd(lcm, arr[i]));
}
result = lcm;
} else {
result = arr[0];
}
return result;
}
public static long lcm(long a, long b, long gcd){
return a*b / gcd;
}
.png)
.png)
댓글
댓글 쓰기