Problem: Universal Base Cycle for N Devices

# Description

You are designing a centralized firmware update for tens of thousands of newly launched "Aqua" brand smart auto-feeders. Currently, N feeders operate on distinct daily feeding schedules, represented by arrays of positive integers. To optimize the firmware's memory footprint, the central server needs to extract and deploy a single "longest common base module" (an integer array) that can perfectly reconstruct every individual feeder's schedule. Specifically, you must find the longest integer array that, when concatenated with itself one or more times, exactly matches each of the N feeder schedules. If no such universal base module exists that satisfies all feeders, return an empty array [].

 

Example 1:

• Input: schedules = [[10, 20, 10, 20], [10, 20], [10, 20, 10, 20, 10, 20]]
• Output: [10, 20]
• Explanation: The base module [10, 20] can be concatenated 2, 1, and 3 times respectively to perfectly reconstruct all given schedules.

Example 2:

• Input: schedules = [[50, 50, 50], [50, 50, 50, 50], [50, 50]]
• Output: [50]
• Explanation: All schedules are multiples of the base module [50]. (Note: [50, 50] cannot reproduce the second schedule).

Example 3:

• Input: schedules = [[15, 30], [30, 15]]
• Output: []
• Explanation: There is no common base module that can be repeated to form both schedules.

Constraints:

• 1 <= N <= 10^4
• 1 <= schedules}[i].length <= 10^4
• schedules[i] consists of positive integers.

---

# Key Points

문제 내용이 복잡해보일 뿐이지 최대공약수를 찾아준다라고 생각하면 단순하게 풀 수 있는 문제이다. 두 가지 포인트를 짚고 넘어가면 된다. 첫 번째로는 두 배열이 공통 모듈을 공유한다면 순서를 바꿔 더해도 결과가 같다는 속성을 이해해야 한다. 이게 무슨 말이냐면 str1+str2나 str2+str1으로 해도 결과적으로 같은 답이 나오냐이다. 두 번째는 N개의 디바이스로 확장하기 위해서 functools의 reduce를 사용하여 상태 변수 없이 전체 데이터에 GCD(최대공약수) 연산을 누적 적용을 한다는 것이다. 결과적으로 별거 아닌(?)것처럼 보이는 문제여도 Data compression and storage optimization, functional programming pattern and scaling out까지를 볼 수 있기 때문에 자주 나오는 기초 문제이고 나 역시도 이 문제를 낼 거 같다.

 

(사실 내가 문제를 좀 응용해서 scaling out까지가 나오는건데 사실 두 번째 포인트인 reduce까지는 나오지는 않을 것이다.)

---

# Solutions

import math
from functools import reduce

class Solution:
    def extractUniversalCycle(self, schedules: list[list[int]]) -> list[int]:
        
        # Helper function to find the Greatest Common Divisor (GCD) of two arrays
        def get_gcd_of_two_arrays(arr1: list[int], arr2: list[int]) -> list[int]:
            # In Python, list concatenation works exactly like string concatenation.
            # If a + b != b + a, they do not share a common repeating pattern.
            if arr1 + arr2 != arr2 + arr1:
                return []
            
            # If they share a pattern, the length of the GCD pattern is 
            # the GCD of their respective lengths.
            gcd_length = math.gcd(len(arr1), len(arr2))
            
            # Slice and return the base module
            return arr1[:gcd_length]

        # Use reduce to iteratively apply the helper function across all N schedules.
        # e.g., reduce(f, [A, B, C]) computes f(f(A, B), C).
        return reduce(get_gcd_of_two_arrays, schedules)

---