package daily

import "slices"

// 20231124
// Problem 1561: Maximum Number of Coins You Can Get
// https://leetcode.com/problems/maximum-number-of-coins-you-can-get
// Difficulty: Medium

// maxCoins returns the maximum number of coins you can get by following the rules below:
// - There are 3n piles of coins of varying size.
// - In each step, you will choose any 3 piles of coins (not necessarily consecutive).
// - Take the second largest pile of coins and add it to your collection.
// - Return the maximum number of coins you can get.
func maxCoins(piles []int) int {
        var ans int
        // Sort the piles in ascending order.
        slices.Sort(piles)
        // Drop the first n/3 piles, as we'll never choose them.
        piles = piles[len(piles)/3:]
        // Sum every other pile, as we'll always choose the largest pile.
        for i := 0; i < len(piles); i += 2 {
                ans += piles[i]
        }
        return ans
}

package daily

import "slices"

// 20231123
// Problem 1630: Arithmetic Subarrays
// https://leetcode.com/problems/arithmetic-subarrays
// Difficulty: Medium

// This solution is not the most efficient, as there's a number theory solution that doesn't
// require sorting. However, this solution is simple and easy to understand, and still passes
// all the test cases in LeetCode.

// checkArithmeticSubarrays returns a slice of booleans indicating whether each subarray
// defined by the given l and r slices is an arithmetic sequence.
func checkArithmeticSubarrays(nums []int, l []int, r []int) []bool {
        var results []bool
        for i := 0; i < len(l); i++ {
                // We need to make a copy of the subarray because we're going to sort it.
                subarray := make([]int, r[i]-l[i]+1)
                copy(subarray, nums[l[i]:r[i]+1])
                results = append(results, isArithmetic(subarray))
        }
        return results
}

// isArithmetic returns true if the given slice of integers is an arithmetic sequence, and
// false otherwise.
func isArithmetic(nums []int) bool {
        // Base cases that don't require sorting.
        if len(nums) < 2 {
                return false
        } else if len(nums) == 2 {
                return true
        }
        // Sort the slice and check if the difference between each pair of numbers is the same.
        slices.Sort(nums)
        diff := nums[1] - nums[0]
        for i := 2; i < len(nums); i++ {
                if nums[i]-nums[i-1] != diff {
                        return false
                }
        }
        return true
}

package daily

// 20231125
// Problem 1685: Sum of Absolute Differences in a Sorted Array
// https://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-array
// Difficulty: Medium

// Turns out calculating the suffix sum wasn't necessary, and likely cost some memory.
// Per a comment on the problem, just the prefix is needed:
// result[i] = (nums[i]*i - pre[i]) + (pre[n]-pre[i] - nums[i]*(n-i))

// getSumAbsoluteDifferences returns an array ans of length n, where ans[i] is the sum of
// absolute differences between nums[i] and all the other elements in the array.
func getSumAbsoluteDifferences(nums []int) []int {
        var (
                ans, prefix, suffix = make([]int, len(nums)), make([]int, len(nums)), make([]int, len(nums))
                n                   = len(nums)
        )
        // Calculate the prefix and suffix sums.
        prefix[0] = nums[0]
        suffix[n-1] = nums[n-1]
        for i := 1; i < len(nums); i++ {
                prefix[i] = prefix[i-1] + nums[i]
                suffix[n-i-1] = suffix[n-i] + nums[n-i-1]
        }
        // We can calculate the answer for each index i by using the prefix and suffix sums.
        for i := 0; i < len(nums); i++ {
                left := i*nums[i] - prefix[i]
                right := suffix[i] - nums[i]*(n-i-1)
                ans[i] = left + right
        }
        return ans
}

package daily

// 20231128
// Problem 2147: Number of Ways to Divide a Long Corridor
// https://leetcode.com/problems/number-of-ways-to-divide-a-long-corridor
// Difficulty: Hard

// numberOfWays returns the number of ways to divide the corridor.
func numberOfWays(corridor string) int {
        var (
                ans, seenSeats, seenPlants int
        )
        // Iterate over each character in the corridor.
        for _, c := range corridor {
                if c == 'S' {
                        seenSeats++
                        if seenSeats == 2 && ans < 1 {
                                // We only start caring about the number of plants when we've seen two seats.
                                ans = 1
                        } else if seenSeats == 3 {
                                // We've seen a third seat, so we sum the answer with seenPlants+1, with the modulo to prevent an overflow.
                                ans = ans * (seenPlants + 1) % (1e9 + 7)
                                // Reset the seen seats and plants.
                                seenSeats = 1
                                seenPlants = 0
                        }
                } else if seenSeats == 2 {
                        // We only care about the number of plants when we've seen two seats.
                        seenPlants++
                }
        }
        // If there are an odd number of seats, then there are no ways to divide the corridor.
        if seenSeats == 1 {
                return 0
        }
        return ans
}

package l75

import (
        "strings"
)

// 20231125
// LeetCode 75
// Problem 1071: Greatest Common Divisor of Strings
// https://leetcode.com/problems/greatest-common-divisor-of-strings
// Difficulty: Easy

// This solution can be simplified further. If str1 + str2 != str2 + str1, then return "".
// If they are equal, str[:gcd] is the greatest common divisor of str1 and str2.

// gcdOfStrings returns the greatest common divisor of strings str1 and str2.
func gcdOfStrings(str1 string, str2 string) string {
        // If str1 == str2, return str1.
        if str1 == str2 {
                return str1
        }
        // If either string is empty, return "".
        if len(str1) == 0 || len(str2) == 0 {
                return ""
        }
        // Find the greatest common divisor of the lengths of str1 and str2.
        gcd := getGCD(len(str1), len(str2))
        gcdStr := str1[:gcd]
        // If str1[:gcd] is a divisor of str1 and str2, return str1[:gcd].
        if str1 == strings.Repeat(gcdStr, len(str1)/gcd) && str2 == strings.Repeat(gcdStr, len(str2)/gcd) {
                return gcdStr
        }
        return ""

}

// getGCD returns the greatest common divisor of two integers.
func getGCD(a, b int) int {
        // Euclidean algorithm
        if a == 0 {
                return b
        }
        return getGCD(b%a, a)
}

package l75

// 20231124
// LeetCode 75
// Problem 1768: Merge Strings Alternately
// https://leetcode.com/problems/merge-strings-alternately
// Difficulty: Easy

// Optimal solution evidently uses a string builder.

// mergeAlternately returns the merge of word1 and word2, where the merge is formed by
// alternating the letters in word1 and word2, starting with word1. If one of the words
// is longer than the other, then the remaining letters in the longer word should be
// appended at the end of the merge.
func mergeAlternately(word1 string, word2 string) string {
        var ans []byte
        // Iterate over the shorter word, then append the remaining letters of the longer word.
        short := min(len(word1), len(word2))
        for i := 0; i < short; i++ {
                ans = append(ans, word1[i], word2[i])
        }

        // Append the remaining letters of the longer word.
        if len(word1) > len(word2) {
                ans = append(ans, word1[short:]...)
        } else if len(word2) > len(word1) {
                ans = append(ans, word2[short:]...)
        }

        return string(ans)
}