DEV Community: Łukasz Kiełczykowski

Project Euler #5 - Going Back To Primary School

Łukasz Kiełczykowski — Wed, 22 Nov 2023 20:23:25 +0000

Project Euler Series

This is a 5th post of ongoing series based on Project Euler.
You can check out the previous post here.

Disclaimer

This blogpost provides solution to the 5th problem from Project Euler.
If you want to figure out a solution yourself, go to the Problem 5's page and come back later :)

When I was in a primary school, I remember we were drawing little tables in Math lessons to find the least common multiple or the greatest common divisor. These looked like this:

A few years later, when I was learning programming the same tasks were used as a programming exercise, in order to practise looping, accumulating and algorithmic thinking. After even more years have passed, here we are figuring out the same concept but for the Project Euler 🥸

The Problem

$2520$ is the smallest number that can be divided by each of the numbers from $1$ to $10$ without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from $1$ to $20$ ?

The Least Common Multiple

The Simplest Solution

What we need to do is to calculate LCM (the least common multiple) for given numbers range. The simplest approach is quite straight forward. Let's see the code:

fun getLeastCommonMultiple(): Long {
    val rangeEnd = 20
    val input = (2..rangeEnd).toList()

    var smallestMultiple = rangeEnd
    while (!smallestMultiple.isDividable(input)) {
        smallestMultiple += rangeEnd
    }
    return smallestMultiple
}

fun Long.isDividable(input: List<Int>): Boolean =
    input.all { mod(it) == 0 }

I decided to use explicit values here, because the problem is well defined and we don't need more general solution, but in that case we could easily parametrize the whole method.

Anyway, as you can see, we accumulate a number and check if it is divisible by all numbers within the given range. It's not very sophisticated solution, but it works. On my computer it calculates the solution in 150ms, which in that case is totally ok, however let's play a little and find a way to speed this up.

Primes... Again...

We've already dealt with prime numbers in the 3rd problem. The given range contains some prime numbers, and in order to have an outcome which will be divisible by all contained prime numbers and the rest, we can create a starting number which is a product of all prime numbers within the range. Any number below the product number isn't divisible by the mentioned prime numbers.

In order to determine these prime numbers, we can run a similar algorith as in the the 3rd problem or even we could implement a sieve algorithm, but the given range is very small and I would suggest provide them by hand.

fun getLeastCommonMultiple(): Int {
    val primes = listOf(2, 3, 5, 7, 11, 13, 17, 19)
    val primesProduct = primes.fold(1) { acc, value -> acc * value}

    val rangeEnd = 20
    val input = (2..rangeEnd).toList()
    var smallestMultiple = primesProduct * rangeEnd

    while (!smallestMultiple.isDividable(input)) {
        smallestMultiple += rangeEnd
    }
    return smallestMultiple
}

You might be wondering why I multiplied the product of primes by $20$ . The reason is simple: in order to find the least common multiple, we must work with multiples of $20$ , the largest number in the given range.

It's still not a sophisticated solution, it's a better version of the first one and on my computer it calculates the solution in around 60ms.

Prime Factorization

The prime factorization is what I did in primary school with mentioned "little tables". We need to find all prime factors of each number from the range and gather only these which occurs the most often. An example should make it clearer.

\begin{aligned} 40 &= 2 * 2 * 2 * 5 \ \newline 36 &= 2 * 2 * 3 * 3 \ \newline LCM(40, 36) &= 2 * 2 * 2 * 3 * 3 * 5 = 360 \end{aligned}

The most important thing to notice here is the number of a given factor. The biggest number of occurrences of a given prime is used for a solution.

fun getLeastCommonMultiple(): Int {
    val primes = listOf(2, 3, 5, 7, 11, 13, 17, 19)
    val resultFactorsBuckets = MutableList(primes.size) { 1 }

    val numbersForFactorization = (2..20).toList() - primes
    numbersForFactorization.forEach { n ->
        var factoredNumber = n
        val factorsBucketsForN = MutableList(primes.size) { 0 }
        primes.forEachIndexed { primeIndex, prime ->
            while (factoredNumber.mod(prime) == 0) {
                factoredNumber /= prime
                factorsBucketsForN[primeIndex]++
            }
            if (factoredNumber == 1) return@forEachIndexed
        }
        for (i in 0 until resultFactorsBuckets.size) {
            if (factorsBucketsForN[i] > resultFactorsBuckets[i]) {
                resultFactorsBuckets[i] = factorsBucketsForN[i]
            }
        }
    }
    return primes.foldIndexed(1) { index, acc, value ->
        acc * value.pow(resultFactorsBuckets[index])
    }
}

fun Int.pow(n: Int): Int =
    toDouble().pow(n).toInt()

I use "buckets" for counting all occurrences of all prime numbers within the given range. I use a temporary "buckets" for a given number as well. This allows me to compare and choose the highest number of occurrences. The last step is to calculate the actual LCM using outcome from "buckets" as an
exponent for given prime number.

This solution is even faster. On my computer it calculates the answer in around 20ms.

The Solution

L CM (2..20) = 232792560

Conclusion

It was nice to explore these simple algorithms and see the improvements in the calculation time. In primary school I never would have thought I'd be coding these little tables, but to be fair I never would have thought I'd be coding in the first place 🤓

Project Euler #4 - Two-Headed Monster

Łukasz Kiełczykowski — Thu, 16 Nov 2023 19:57:33 +0000

Project Euler Series

This is a 4th post of ongoing series based on Project Euler.
You can check out the previous post here.

Disclaimer

This blogpost provides solution to the 4th problem from Project Euler.
If you want to figure out a solution yourself, go to the Problem 4's page and come back later 😌

This time we have another very popular problem to solve. A palindrome, but with a nice twist. Usually, it's about strings and this one is about numbers.

It's going to be a short one, so let's get to it 😇

The Problem

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is $9009 = 91 * 99$ .

Find the largest palindrome made from the product of two 3-digit numbers.

Am I a Palindrome?

Classic, simple algorithmic problem to solve. Is something the same when read from the beginning to the end as when read from the end to the beginning. As you can imagine, checking an integer is as simple as checking a single word 🤓

We need to change the input into a string.
When the input has an even length, then we simply divide it into two parts, otherwise we take the biggest even half from both sides.
If the left side is the same as reversed right side, we have a palindrome!

Show Me The Code!

Ok, ok, here you go 😇

fun isPalindromeNumber(value: Int): Boolean {
    val valueInString = value.toString()
    val valueSize = valueInString.length
    val comparisonCellLength = valueSize / 2
    val leftSide = valueInString.subSequence(
        startIndex = 0,
        endIndex = comparisonCellLength,
    )

    val rightSide = valueInString.subSequence(
        startIndex = valueSize - comparisonCellLength,
        endIndex = valueSize,
    ).reversed().toString()

    return leftSide == rightSide
}

Super simple ❤️

Glue Everything Together

In order to get the solution we need to use the isPalindromeNumber for every product of two numbers from $100$ to $999$ . Additionally, just out of curiosity, we can get an information how many palindromes has a given configuration.

fun getPalindromes(): List<Int> {
   val bottom = 100
   val top = 999

   val palindromes = mutableListOf<Int>()
   for (i in top downTo bottom) {
      for (j in top downTo bottom) {
         val result = i * j
         if (isPalindromeNumber(result)) {
            palindromes.add(result)
         }
      }
   }

   return palindromes
}

// Print the solution
println(getLargestPalindrome().maxOrNull())

The Solution

The answer to the problem is: 906609 and there are 2470 palindromes within the given setup.

Conclusion

Yet another classic problem to solve, however with a nice twist. That concludes the 4th problem. Nothing more interesting to share here. Just remember the set is created from a product of two numbers and not it's not a range from $100 * 100$ to $999 * 999$ .

Project Euler #3 - to Sieve or not to Sieve

Łukasz Kiełczykowski — Sat, 04 Nov 2023 19:29:12 +0000

Project Euler Series

This is a 3rd post of ongoing series based on Project Euler.
You can check out the previous post here.

Disclaimer

This blogpost provides solution to the 3rd problem from Project Euler. If you want to figure out a solution yourself, go to the Problem 3's page and come back later :)

The time has come to tackle prime numbers. Let's see what's the 3rd task.

The Problem

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Prime numbers

If you're here, then probably, it's not a secret for you what a prime number is. However, just to have a full picture, let's define it. It's a number greater than 1, and it has only two factors: 1 and itself.

Be cautious, because 2 is a prime number as well! Somehow, I tricked my brain into thinking it's not because it's even, ha! What a mistake...

Am I prime?

Determining if a number is prime is a fundamental problem in number theory and computer science. There are a few options, but we will focus on the simplest ones a trial division. At first, I thought about using a sieve algorithm, however after analysis, it would be slower and memory consuming. To be fair, it would be good choice for getting a list of primes, but not to test if one is.

Basic Trial Division

In order to figure out if given number is a prime one we can make sure it has no factors beyond 1 and itself.

private fun isPrime(value: Long): Boolean {
    if (value < 2L) return false

    val checkBoundary = sqrt(value.toDouble()).toInt()

    val isDividable = (2..checkBoundary).any {
        value.mod(it) == 0
    }

    return !isDividable
}

First of all, look at the type of an input. We know the number for which we do the calculation, so we could choose Int as we do this test for a number up to $600851475143\sqrt{600851475143}$ (from the problem's description) - below Int's limit. The Long type is here only to have less casting, because as you can see, the input is above Int's limit.

Next thing is to perform this test only on factors of the given number. What's more, we are looking for the biggest prime factor, that's why we can perform the test starting from the end of factors collection. This will decrease number of checks.

private fun getBiggestPrimeFactorOf(input: Long): Long {
    val checkBoundary = sqrt(input.toDouble()).toLong()

    val factors = (2..checkBoundary).filter {
        input.mod(it) == 0L
    }

    return factors
        .reversed()
        .first(::isPrime)
}

This code gives us correct answer:

val input = 600_851_475_143L
val solution = getBiggestPrimeFactorOf(input)
println(solution) // 6857

Complexity Analysis

Let's dive into determining time complexity.

First, we get list of factors and that's a $O(n)O(\sqrt{n})$ complexity. Then, in the worst case scenario, we will perform a check for each factor which is $n\sqrt{n}$ times. Single primality check with our method is a $O(m)O(\sqrt{m})$ where $m$ is a factor number. In the worst case scenario $\sqrt{n}$ . Hence, single check is:

O(\sqrt{\sqrt{n}}) = O(n^\frac{1}{4})

and with that, the whole complexity is:

O(\sqrt{n} * n^\frac{1}{4}) = O(n^\frac{3}{4})

Conclusion

It was still quite an easy problem to solve. However, interesting for me was the realisation that the sieve algorithm is not a great choice and I needed some time to figure out why it took a few times longer for the sieve to determine the biggest prime factor than the simple division.

Project Euler #3 - to Sieve or not to Sieve

Łukasz Kiełczykowski — Sat, 04 Nov 2023 19:29:12 +0000

Project Euler Series

This is a 3rd post of ongoing series based on Project Euler.
You can check out the previous post here.

Disclaimer

This blogpost provides solution to the 2nd problem from Project Euler. If you want to figure out a solution yourself, go to the Problem 3's page and come back later :)

The time has come to tackle prime numbers. Let's see what's the 3rd task.

The Problem

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Prime numbers

Be cautious, because 2 is a prime number as well! Somehow, I tricked my brain into thinking it's not because it's even, ha! What a mistake...

Am I prime?

Basic Trial Division

In order to figure out if given number is a prime one we can make sure it has no factors beyond 1 and itself.

private fun isPrime(value: Long): Boolean {
    if (value < 2L) return false

    val checkBoundary = sqrt(value.toDouble()).toInt()

    val isDividable = (2..checkBoundary).any {
        value.mod(it) == 0
    }

    return !isDividable
}

private fun getBiggestPrimeFactorOf(input: Long): Long {
    val checkBoundary = sqrt(input.toDouble()).toLong()

    val factors = (2..checkBoundary).filter {
        input.mod(it) == 0L
    }

    return factors
        .reversed()
        .first(::isPrime)
}

This code gives us correct answer:

val input = 600_851_475_143L
val solution = getBiggestPrimeFactorOf(input)
println(solution) // 6857

Complexity Analysis

Let's dive into determining time complexity.

O(\sqrt{\sqrt{n}}) = O(n^\frac{1}{4})

and with that, the whole complexity is:

O(\sqrt{n} * n^\frac{1}{4}) = O(n^\frac{3}{4})

Conclusion

Project Euler #2 - does Fibonacci have a tail?

Łukasz Kiełczykowski — Thu, 29 Dec 2022 11:12:47 +0000

Project Euler Series

This is a second post of ongoing series based on Project Euler.
You can check out the previous post here.

Disclaimer

This blogpost provides solution to the 2nd problem from Project Euler. If
you want to figure out a solution yourself, go to the
Problem 2's page and come back later :)

The 2nd task is a bit more complex than the previous one, especially for a
person who hasn't dealt with typical algorithmic problems. This one touches
Fibonacci sequence!

The Problem

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not
exceed four million, find the sum of the even-valued terms.

The Fibonacci Sequence is a common example for recursive algorithm's
implementation. If you want to get an n value from the sequence your
implementation may look something like this:

private fun fib(n: Int): Int =
    if (n <= 1) {
        n
    } else {
        fib(n - 1) + fib(n - 2)
    }

However, in our problem, we need to get every value from the sequence until
4_000_000, in order to check if it is even and sum them. So, we
definitely need some accumulator.

The Solution

private tailrec fun sumOfEvenFibonacciNumbers(
    evenAcc: Int,
    prev: Int,
    current: Int,
    top: Int
): Int {
    val next = prev + current
    return if (next >= top) {
        evenAcc
    } else {
        val newAcc = if (next.isEven()) {
            evenAcc + next
        } else {
            evenAcc
        }
        sumOfEvenFibonacciNumbers(
            evenAcc = newAcc,
            prev = current,
            current = next,
            top = top,
        )
    }
}

private fun Int.isEven() = mod(2) == 0

In order to get the solution I call it like this:

println(
    sumOfEvenFibonacciNumbers(
        evenAcc = 0,
        prev = 1,
        current = 1,
        top = 4_000_000,
    )
)

tailrec

Maybe, you noticed I used tailrec. In that case, it's not really
needed, but I added it as a fun fact 🥸 tailrec is an information to the
kotlin's compiler that our function is a tail-recursive function. This means,
we can implement our algorithm using recursion without being scared about
the StackOverflowException and the compiler will rewrite it into
imperative manner.

This sounds great, however a function must be written in a
certain way. The recursive call must happen at the end of the function. In
other words, the recursive call must be the last thing a function does. You
can read more about it in the Kotlin's docs
and on this blog.

Conclusion

Different approach to dealing with the Fibonacci sequence was fun and
allowed to explore recursion again which I haven't used for some
time.

I invite you to continue this little journey with Project Euler to not only
figure out next problems but to have fun with some concepts and sometimes
dig deeper.

Cheers 😎

Project Euler #1 - are we fizz-buzzing?

Łukasz Kiełczykowski — Tue, 27 Dec 2022 10:18:31 +0000

Disclaimer

This blogpost provides solution to the first problem from Project Euler. If
you want to figure out a solution yourself, go to the
Problem 1's page and come back later :)

This is going to be a very brief post as the problem is very simple as well.
It's similar to pretty well known FizzBuzz problem, which is a basic
recruiting task or a simple task at the beginning of one's programming-learning journey.

The Problem

If we list all the natural numbers below 10 that are multiples of 3 or 5,
we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

The simplest O(n) solution would be iteration over the numbers and find multiples of 3 and 5.

Solution

The simplest solution using a loop would like something like this:

private fun loopApproach(input: Int): Int {
    var acc = 0
    for (i in 3 until input) {
        if (i.mod(3) == 0 || i.mod(5) == 0) {
            acc += i
        }
    }

    return acc
}

To be more kotlin you could use fold instead of usual for-loop:

private fun foldApproach(input: Int): Int =
    (3 until input).fold(0) { acc, value ->
        if (value.mod(3) == 0 || value.mod(5) == 0) {
            acc + value
        } else {
            acc
        }
    }

The fold, however, is a bit slower. With large input value
(1_000_000_000 instead of 1_000 and I need use Long for that) which takes in both cases almost 3 seconds on my computer, the difference is over
100ms.

Conclusion

The simplest problem is done. Let's move on to the next and let's see what we can get out of it.

Thank you for your time and see you in the next one!

Cannot find a parameter with this name: message

Łukasz Kiełczykowski — Wed, 26 Jan 2022 15:59:44 +0000

Used Kotlin plugin: 203-1.5.30-release-411-AS7717.8
Used Kotlin version: 1.5

It was a calm beginning of a workday. I sat down to my computer and I started coding. I needed to add a custom Exception class to have logs and a code more readable. You've probably done this many many times.

Usual exception in Kotlin:

data class SomeCustomException(
    val explanation: String
) : Exception(
    message = "Oh, something broke because $explanation"
)

Now, stop for a second and try to figure out what's wrong with that code.

The code above is not marked by the Android Studio as an error. However, when you try to compile this, it will fail with a message Cannot find a parameter with this name: message.

I removed the name message from parameters

data class SomeCustomException(
    val explanation: String
) : Exception(
   "Oh, something broke because $explanation"
)

and it compiles just fine. The question is why?

Apparently, this is a known issue. The IDE treats the Exception class as Kotlin's, but it's just an alias for Java's Exception class. The IDE would have shown you an error, if you had used Java import:

data class SomeCustomException(
    val explanation: String
) : java.lang.Exception(
   message = "Oh, something broke because $explanation" // pointed out as an error by the IDE
)

Maybe for some. of you it's obvious - duh, of course it will fail 🧐 - but I added the named parameter without even thinking.

I hope you are having a great day, without surprising failures ✌🏻