- devlog - purnasatria.dev

GCD

Brute Force

func gcd(a,b int) int {
	for b != 0 {
		a,b = b, a%b
	}
	return a
}

Recursive

func gcd(a,b int) int {
	if a == 0 {
		retrun b
	}
	return gcb(b%a, a)
}

Code Problem

source

For two strings s and t, we say “t divides s” if and only if s = t + t + t + ... + t + t (i.e., t is concatenated with itself one or more times). Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.
Example 1: Input: str1 = “ABCABC”, str2 = “ABC” Output: “ABC”
Example 2: Input: str1 = “ABABAB”, str2 = “ABAB” Output: “AB”
Example 3: Input: str1 = “LEET”, str2 = “CODE” Output: ""
Constraints:
1 <= str1.length, str2.length <= 1000
str1 and str2 consist of English uppercase letters.

Solution

func gcdOfStrings(str1 string, str2 string) string {
    a := len(str1)
    b := len(str2)
    
    if str1 + str2 != str2 + str1{
        return ""
    }
    
    i := gcd(a,b)
    
    return str1[:i]
    
    
}

func gcd(a,b int) int {
    if a == 0 {
        return b
    }
    return gcd(b%a, a)
}

log / euclidean algorithm - great common divisor

GCD

Brute Force

Recursive

Code Problem

Solution

Reference