Skip to main content

Oracle

Oracle OA 2023 - Female Codebreaker


Elizabeth Smith Friedman was an American cryptanalyst who deciphered enemy codes in both World Wars. Greatest Common Divisor (GCD) finds a variety of applications in cryptographic algorithms.

For the multiset of positive integers (a = (a_1, a_2, ..., a_k)), let the GCD of (a) be defined as (x), where (x) is the maximum positive integer such that all the integers in the multiset (a) are divisible by (x).

Given a sequence of (n) integers arr, find the subarray of length greater than 1 whose GCD is the maximum possible. If there exist multiple subarrays, then choose the largest in length.

Output the maximum possible GCD and the corresponding maximum possible length of this GCD.

Function Description:

Complete the function gcdArrays in the editor below.

gcdArrays has the following parameter(s):

  • int arr[n]: an array of integers.

Returns:

  • int[]: the maximum possible GCD and the corresponding maximum possible length of this GCD.

Constraints:

  • 1 ≤ n ≤ 10^5
  • 1 ≤ arr[i] ≤ 10^9