sudopower

lc_3556

LC: 3556: Sum of Largest Prime Substrings

Link to problem

Solution 1

func sumOfLargestPrimes(s string) int64 {
    var nos []int
    s = strings.Trim(s, "0")    
    
    for idx := range s{
        var curStr string
        if curStr=="0"{
            continue
        }
        
        for i:=idx;i<len(s);i++{
            curStr+=string(s[i])
            no,_:=strconv.Atoi(curStr)
            nos=append(nos,no)            
        }
    }

    if len(s)==1{        
        x,_:=strconv.Atoi(string(s[0]))
        nos=append(nos,x)
    }

    var primes []int
    for _,no := range nos{
        if big.NewInt(int64(no)).ProbablyPrime(0) {
            primes = append(primes,no)
        }    
    }

    if len(primes)==0{
        return 0
    }
    
    slices.Sort(primes)
    uniqPrimes := slices.Compact(primes)
    slices.Reverse(sort.IntSlice(uniqPrimes))
    
    if len(uniqPrimes)>2{
        return int64(uniqPrimes[0]+uniqPrimes[1]+uniqPrimes[2])
    }
    
    return int64(sumListRecursive(uniqPrimes))            
}

func sumListRecursive(numbers []int) int {    
    if len(numbers) == 0 {
        return 0
    }
    return numbers[0] + sumListRecursive(numbers[1:])
}

Possible optimisations-

  1. Faster prime calc, subs string to num generation
  2. avoid duplicates using map

Leave a Reply

Your email address will not be published. Required fields are marked *

Related Blogs