Road to Genius: superior #58

Each day I solve several coding challenges and puzzles from Codr's ranked mode. The goal is to reach genius rank, along the way I explain how I solve them. You do not need any programming background to get started, and you will learn a ton of new and interesting things as you go.

let S = 0;
for (let i = 0; i < 192; i++) {
  let h = Math.floor(i/2)
  if (h > 0)
    S += i % h
}

// S = ? (number)

Today's coding challenge is a very interesting one, because we need to play smarter than usual to solve it. It's only a few lines of code but we need a strategy to solve it.

The for-loop iterates 192 times which is quite a lot, so doing it in our heads, paper or excel will be a huge overkill. Let's start by briefly analyzing what the code does in pseudo-code:

S = 0
for i in [0 to 192]:
  h = floor(i/2)
  S += i % h
return S

The variable h is half of i. The remainder from dividing i by h is added to S. Let's do a few iterations to illustrate this:

i:0 S+=0
i:1 S+=0
i:2 S+=0
i:3 S+=0
i:4 S+=0
i:5 S+=1
i:6 S+=0
i:7 S+=1
i:8 S+=0
i:9 S+=1

i:10 S+=0
i:11 S+=1
i:12 S+=0
i:13 S+=1
i:14 S+=0
i:15 S+=1
i:16 S+=0
i:17 S+=1
i:18 S+=0
i:19 S+=1

Notice that the numbers [0, 9] produce three ones. But everything else, that is [10, 19] produce five ones. The same is true for [20, 29], and so on... In a nutshell this algorithm is related to the number of odd numbers within the range, with the exception of the first ten numbers:

The first 10 numbers (0 to 9) produce 3 odd numbers.

The next 90 numbers (10 to 99) produce 9*5=45 odd numbers.

The next 90 numbers produce once again 45 odd numbers.

The last 2 numbers (190 to 192) produce 1 odd number.

3 + 45 + 45 + 1 = 94

By solving these challenges you train yourself to be a better programmer. You'll learn newer and better ways of analyzing, debugging and improving code. As a result you'll be more productive and valuable in business. Get started and become a certified Codr today at https://nevolin.be/codr/