Coding Challenge #7: Pairs divisible by 5

Coding Challenge #7

Welcome back, to another coding challenge! At this point, these challenges are made for beginners, so really sorry if you didn’t find what you’re looking for! Have fun

As usual, same requirements:

• Has to be written in Lua 5.1 (the version roblox uses)
• The program has to be compatible with Roblox Studio, meaning you can’t use features vanilla Lua has but rbxlua disabled
• You can’t use httpservice to cheat the challenge

Given two integers `x` and `y`, write a function `pairsDivisibleBy5(x, y)` that returns the number of all pairs (`m`, `n`) where `1 ≤ n ≤ y` and `1 ≤ m ≤ x` that satisfy `(m+n)%5==0`.

``````pairsDivisibleBy5(6, 12) --14
pairsDivisibleBy5(11, 14) --31
pairsDivisibleBy5(553, 29) --3208
pairsDivisibleBy5(2, 2) --0
``````

Goodluck! You can find a list of all the challenges here or a github version here.

``````local function pairsDivisibleBy5(x, y)
local pairs = {}
for i = 1, x do
for j = 1, y do
table.insert(pairs, (i+j)%5==0 and true or nil)
end
end
return #pairs
end
``````
5 Likes

The solution provided in this question is over-complicated. The time and space complexity of their solution is extremely inefficient (especially since the solution is O(n^2)). It could easily be simplified to a more efficient solution using simple modular arithmetic and integer rounding. Moreover, the solution could easily be simplified to a time complexity of O(1), thus the solution provided is terrible since it supports writing inefficient code.

Ooh, an interesting one. By solving the easy ones manually, I figure that repeats still count.

``````local function pairComponent(number)

local counterTable, counter = {}, 0

repeat

counter = counter + 1
table.insert(counterTable, counter)

until counter > number - 1

return counterTable

end

local function isDivBy5(m, n)

local valid = {}

for i, v in pairs(m) do

for j, k in pairs(n) do

if (v + k) % 5 == 0 then table.insert(valid, {v, k}) end

end

end

return valid

end

local function pairsDivisibleBy5(x, y)

local m, n = pairComponent(x), pairComponent(y)

return #isDivBy5(m, n)

end

print(pairsDivisibleBy5(553, 29)) --3208, same as yours!
``````

So, it seems to work, it’s just a matter of efficiency. Time to check the answer!

Edit: Looks like I took the longer away…

2 Likes

O(1)

``````local function pairsDivisibleBy5(a, b)
local x, y = a%5, b%5
local i, j = (a-x)/5, (b-y)/5
return 5*i*j + i*y + j*x + math.max(0, x+y-4)
end
``````
9 Likes

You never specified any constraints for `m` and `n`, Your constraints for `m` and `n` are loose, so they could both be decimal numbers.

code
``````local function pairsDivisibleBy5(x, y)
return (x + y > 5 and math.huge) or (x + y == 5 and 1) or 0
end
``````
6 Likes

Took me a while to figure this out, but finally after staring at my matrix for long enough,

``````local Round = function(x, y)
return (x - x%y)/y
end