HackerRank Number Theory – The Chosen One

Challenge: The Chosen One

Subdomeniu: Number Theory (number-theory)

Scor cont: 40.0 / 40

Submission status: Accepted

Submission score: 1.0

Submission ID: 464736855

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/the-chosen-one/problem

Cerinta

You are given a sequence of $n$ integers, $a_0, a_1, \ldots, a_{n-1}$. Find and print any integer $x$ such that $x$ is divisor of every $a_i$ except for exactly one element.

Input Format

The first line contains an integer, $n$, denoting the length of the sequence.		
The second line contains $n$ positive space-separated integers describing $a_0, a_1, \ldots, a_{n-1}$.

Output Format

Print any positive integer denoting $x$ such that $x$ is a divisor of exactly $n-1$ of the sequence's elements. $x$ must be between $1$ and $2 \cdot 10^{18}$

Constraints

- $1 \le n \le 10^5$
- $1 \le a_i \le 10^{18}$
- It is guaranteed that a solution exists.

Cod sursa

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

long long getDivisor(long long a[], long long n) { 
    
    if (n == 1) 
        return (a[0] + 1);   
    long long prefix[n], suffix[n];   
    
    prefix[0] = a[0]; 
    for (long long i = 1; i < n; i++)  
         prefix[i] = __gcd(a[i], prefix[i - 1]);    
  
    
    suffix[n-1] = a[n-1]; 
    for (long long i = n - 2; i >= 0; i--)  
         suffix[i] = __gcd(suffix[i + 1], a[i]);    
      
    for (long long i = 0; i <= n; i++) {   
        long long t = 0;          
        if (i == 0) 
            t = suffix[i + 1]; 
        else if (i == n - 1) 
            t = prefix[i - 1]; 
        else
            t = __gcd(prefix[i - 1], suffix[i + 1]);   
        
        if (a[i] % t != 0) 
            return t; 
    } 
  
    return 0LL; 
} 


int main(){
    long long n = 1;
    cin >> n;
    long long a[n];
    for(long long i=0;i<n;i++) cin >> a[i];

    cout << getDivisor(a,n) << '\n';
    return 0;
}