Coding Challenge #7: Pairs divisible by 5

Resources Community Tutorials
#1

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.
98e6477fa0a6a4ff482b43177d1c8e2abbc4d9df

Answer! 
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
#3

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.

#4

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
#5

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
#6

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
#7

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

local Answer = function(x, y)
	return(   Round(x+1, 5)*y + ((x+1)%5 -1)*Round(y+1, 5)   )
end
1 Like
#8

Ahahahaha I wish I saw that, nice catch.

Still I find it funny that the solution takes almost as many characters as for the integer-bounded expression.

1 Like