We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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
}
**
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
String Transmission
You are viewing a single comment's thread. Return to all 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 {
} **