String Transmission Discussions | Algorithms | HackerRank
  • + 0 comments

    Hey community, I created a solution that passes all tests except test 10. I’ve checked it in various ways, and it works fine in my compiler, but on HackerRank it returns the wrong answer. Has anyone experienced something similar? (solution in swift language)

    ** func stringTransmission(k: Int, s: String) -> Int {

    let MOD = 1_000_000_007
    let N = s.count
    let sChars = Array(s)
    
    func modAdd(_ a: Int, _ b: Int) -> Int {
        let res = a + b
        return res >= MOD ? res - MOD : res
    }
    func modSub(_ a: Int, _ b: Int) -> Int {
        let res = a - b
        return res < 0 ? res + MOD : res
    }
    func modMul(_ a: Int, _ b: Int) -> Int {
        return Int((Int64(a) * Int64(b)) % Int64(MOD))
    }
    func modPow(_ base: Int, _ exp: Int) -> Int {
        var result = 1
        var b = base
        var e = exp
        while e > 0 {
            if e & 1 == 1 { result = modMul(result, b) }
            b = modMul(b, b)
            e >>= 1
        }
        return result
    }
    func modInv(_ a: Int) -> Int {
        return modPow(a, MOD - 2)
    }
    
    var fact = [Int](repeating: 1, count: N + 1)
    var invFact = [Int](repeating: 1, count: N + 1)
    for i in 1...N {
        fact[i] = modMul(fact[i - 1], i)
    }
    invFact[N] = modInv(fact[N])
    for i in stride(from: N - 1, through: 1, by: -1) {
        invFact[i] = modMul(invFact[i + 1], i + 1)
    }
    func binomial(_ n: Int, _ k: Int) -> Int {
        if k > n || k < 0 { return 0 }
        return modMul(fact[n], modMul(invFact[k], invFact[n - k]))
    }
    
    func divisors(_ n: Int) -> [Int] {
        var divs = [Int]()
        var i = 1
        while i * i <= n {
            if n % i == 0 {
                divs.append(i)
                if i != n / i {
                    divs.append(n / i)
                }
            }
            i += 1
        }
        return divs.sorted()
    }
    
    func mobius(_ n: Int) -> Int {
        if n == 1 { return 1 }
        var n = n
        var lastPrime = 0
        var count = 0
    
        var i = 2
        while i * i <= n {
            if n % i == 0 {
                if lastPrime == i { return 0 }
                lastPrime = i
                count += 1
                n /= i
                if n % i == 0 { return 0 }
            }
            i += 1
        }
        if n > 1 {
            if n == lastPrime { return 0 }
            count += 1
        }
        return (count % 2 == 0) ? 1 : -1
    }
    
    func countPeriodic(d: Int) -> Int {
        var pairs = [(diff0: Int, diff1: Int)]()
        for j in 0..<d {
            var zeroCount = 0
            var oneCount = 0
            var pos = j
            while pos < N {
                if sChars[pos] == "0" { zeroCount += 1 }
                else { oneCount += 1 }
                pos += d
            }
            pairs.append((diff0: oneCount, diff1: zeroCount))
        }
    
        var dp = [Int](repeating: 0, count: k + 1)
        dp[0] = 1
    
        for (diff0, diff1) in pairs {
            var newDp = [Int](repeating: 0, count: k + 1)
            for cost in 0...k {
                let ways = dp[cost]
                if ways == 0 { continue }
                if cost + diff0 <= k {
                    newDp[cost + diff0] = modAdd(newDp[cost + diff0], ways)
                }
                if cost + diff1 <= k {
                    newDp[cost + diff1] = modAdd(newDp[cost + diff1], ways)
                }
            }
            dp = newDp
        }
    
        var res = 0
        for cost in 0...k {
            res = modAdd(res, dp[cost])
        }
        return res
    }
    
    func modPow2(_ exp: Int) -> Int {
        return modPow(2, exp)
    }
    
    if k >= N {
        let divs = divisors(N)
        var answer = 0
        for d in divs {
            let m = mobius(N / d)
            if m == 0 { continue }
            let ways = modPow2(d)
            if m == 1 {
                answer = modAdd(answer, ways)
            } else {
                answer = modSub(answer, ways)
            }
        }
        return answer
    }
    
    let divs = divisors(N)
    var answer = 0
    for d in divs {
        let m = mobius(N / d)
        if m == 0 { continue }
        let c = countPeriodic(d: d)
        if m == 1 {
            answer = modAdd(answer, c)
        } else if m == -1 {
            answer = modSub(answer, c)
        }
    }
    return answer
    

    } **