Google SWE Online Coding Challenge Internship 2021

GOCC15: Google SWE Online Coding Challenge Internship 2021 - GeeksforGeeks

 

✔️ Second Question: Divisibility Count

Find the number of N digit integers divisible by both X and Y, print answer modulo 10^9+7

• Input Format: The first line contains T denoting the number of test cases. The first line of each test case contains 3 integers N, X, Y.
• Output Format: Print an integer denoting the output.

Example

Input	Output
2 2 5 7 1 2 3	2 1

 

🎈 Question

X, Y로 모두 나누어 떨어지는 N자리 정수의 개수를 출력하는 문제

 

🎈 Solution

최소공배수, 최대공약수를 이용하면 빠르게 풀 수 있는 문제이다.

이에 관한 내용을 자세하게 정리해놓은 적이 있어서 쉽게 풀 수 있었다.

[2609] 최대공약수와 최소공배수

 

1. 최소공배수를 찾는다.

최소공배수 = X * Y / 최대공약수 

위의 성질을 참고하여 최소공배수를 쉽게 찾을 수 있고 최대공약수는 유클리드 호제법을 사용하여 구하면 된다.
(자세한 설명은 위의 링크 참조)

2. for문을 돌면서

i에 num을 계속 더하고

이 값이 N자리를 넘지 않을 때까지 cnt를 1씩 증가시킨다.

3. 최종 cnt를 10^9+7로 나눈 수를 ans 배열에 삽입한다.

4. 정답 출력

 

💡 pow

<cmath> 헤더의 내장 함수

pow return 타입이 double이기 때문에 cnt와 연산을 하기 위해서 int로 타입캐스팅 필요!

 

🎈 Time Complexity

gcd → O(logN)

count → O(10^N/최대공약수)

최종 시간복잡도: O(10^N/최대공약수)

 

🎈 Space Complexity

gcd 함수 한 번 실행시에 12byte가 필요하고(a, b, 리턴 값) 이 함수가 평균 logN만큼 반복되므로 12logN만큼의 공간이 필요하고

따라서 공간복잡도는 O(logN) 

 

🎈 Code(C++)

// Google SWE Online Coding Challenge Internship 2021
// https://www.geeksforgeeks.org/gocc15-google-swe-online-coding-challenge-internship-2021/?ref=rp
// Divisibility Count

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector <int> ans;

// 최대공약수
int gcd(int a, int b)  
{ 
    return (a % b)!=0 ? gcd(b, a%b) : b; // 유클리드 호제법 
}

// Find the number of N digit integers divisible by both X and Y
void count(int n, int x, int y)
{
    int cnt = 0, num;
    num = x*y / gcd(x, y); // 최소공배수

    for(int i = num ; i < pow(10, n) ; i+=num) {
        if(i > pow(10, n-1)) {
            cnt++;
        }
    } 
    ans.push_back(cnt % ((int)pow(10, 9) + 7));
}

int main(void)
{
    int t, n, x, y;
    cin >> t; // test case
    
    while(t--) {
        cin >> n >> x >> y;
        count(n, x, y);
    }

    for(int i = 0 ; i < ans.size() ; i++) {
        cout << ans[i] << '\n';
    }
}