[LeetCode/Easy] 2748. Number of Beautiful Pairs

1. Input

1) int[] nums

 

2. Output

1) i<j인 nums[i]와 nums[j]에 대해서, nums[i]의 첫 번째 숫자와 nums[j]의 마지막 숫자가 아름다운 순서쌍인 개수를 반환

- 두 수가 아름다운 순서쌍이라는 것은 두 수가 서로소인 것을 말한다.

- 서로소는 최대공약수가 1인 두 수의 관계를 말한다.

 

3. Constraint

1) 2 <= nums.length <= 100

2) 1 <= nums[i] <= 9999

3) nums[i] % 10 != 0

 

4. Example

Input: nums = [11,21,12] -> Output: 2

설명: 순서쌍의 후보는 총 3개이다.

- i=0, j=1 : 1과 1의 최대공약수는 1이므로 서로소이다.

- i=0, j=2 : 1과 2의 최대공약수는 1이므로 서로소이다.

- i=1, j=2 : 2와 2의 최대공약수는 2이므로 서로소가 아니다.

 

5. Code

class Solution {
    public int countBeautifulPairs(int[] nums) {
        int count = 0;
        for(int i=0 ; i<nums.length-1 ; i++)
            for(int j=i+1 ; j<nums.length ; j++){
                int n = nums[i], x = 0, y = nums[j]%10;
                while(n>0){
                    x = n%10;
                    n /= 10;
                }
                if(gcd(x,y)==1)
                    count++;
            }
        return count;
    }

    static int gcd(int a, int b){
        if(a==1 || b==1) return 1;
        for(int i=Math.min(a,b) ; i>1 ; i--)
            if(a%i==0 && b%i==0)
                return i;
        return 1;
    }
}

- 48%, 98%