4
\$\begingroup\$

The number fizz buzz is composed of two numbers that are fizz and buzz.

fizz represents the numbers that are divisible by 3 and buzz are the numbers that are divisible by 5.

combining both fizz buzz are the numbers that are divisible by both 3 and 5 both. So how can we get all the fizz buzz numbers sum in a given range?

If we analyze and try to find out the numbers that are divisible by both 3 and 5 we get series like this:

3*5*1, 3*5*2, 3*5*3, .....,3*5*n

analyzing this here is my C# code to find all fizz buzz numbers sum in a given range.

I am looping through the entire range and add all numbers whose remainder with 15 is 0.

int start_range = Convert.ToInt32(Console.ReadLine());
int end_range = Convert.ToInt32(Console.ReadLine());
int sum = 0;
for(int i= start_range; i<= end_range; i++)
{
    if(i%15==0)
    {
        sum = sum + i;
    }
}
Console.WriteLine(sum);
Console.ReadKey();
\$\endgroup\$
  • 3
    \$\begingroup\$ Try to use the fact that \$15+30+45+...+15n = 15(1+2+3+...+n) = 15\frac{n(n+1)}{2}\$, which should give you the optimal solution. Explanation can be found here. \$\endgroup\$ – maxb Aug 22 '18 at 11:29
  • \$\begingroup\$ thank you for your interest in my question and providing this optimized solution for this problem. \$\endgroup\$ – vijay pratap Aug 22 '18 at 11:43
  • 1
    \$\begingroup\$ This problem is very similar to Project Euler 1, which begs the question if the fizzbuzz numbers are the numbers which are divisible by either 3 or 5, instead of both of them. If that's not the case, your code solves the task, and the optimization above should make it lightning fast. \$\endgroup\$ – maxb Aug 22 '18 at 12:05
7
\$\begingroup\$

I don't have much to say for the code itself, it is concise, readable and does what you want it to do. That's a good start. My only critique is that you handle input and output in the same place, if you plan on reusing the code maybe consider making a method.


So since the code is on point, we can look at the algorithm you are using. The only time the sum will change is when the sequence passes a multiple of 15. So lets see if we can find which multiples of 15 are between our starting point (x) and our ending point (y).

If we start at x, the first multiple of 15 we will encounter will be

$$15 \lceil \frac{x}{15} \rceil$$

To give you some intuition as to why this is the case, my argument is as follows. When you divide a number by 15, you get a whole part (how many 15s you can make from x) and a remainder (how many are left over when you make as many 15s from x as you can). The next multiple of 15 after (or including) x will be the first number you get when counting upwards who's remainder is 0. In other words, the remainder is a progress bar of how close to 15 we are. By taking the ceiling of x / 15, we are setting the progress bar to full, so when we multiply by 15 we get the next multiple.

What is the last multiple before (or including) y? We can use similar logic to get

$$15 \lfloor \frac{y}{15} \rfloor$$

And now we can directly loop over multiples of 15, no need to do any mods.

int start = 15 * (int)Math.Ceiling((double)start_range / 15);
int end = 15 * (int)Math.Floor((double)end_range / 15);
int sum = 0;
for (int i = start; i <= end; i += 15) {
    sum += i;
}

We don't have to stop there. This is a straightforward enough sum so we can somewhat simplify it.

$$start + (start + 15) + (start + 30) + ... + end$$

We can write start and end as multiples of 15 (where a and b are just integers).

$$15a + (15a + 15) + (15a + 30) + ... + 15b$$

We will now factor out 15 term.

$$15(a + (a + 1) + (a + 2) + ... + b)$$

int a = (int)Math.Ceiling((double)start_range / 15);
int b = (int)Math.Floor((double)end_range / 15);
int sum = 0;
for (int i = a; i <= b; i++) {
    sum += i;
}
sum *= 15;

I think the sum is simple enough now that we can do it without a loop. I'm going to "cheat" a little and just introduce the identity we will use without much explanation. There are some nice visualizations and proofs online if you want to look them up yourself.

$$ a, b \in \mathbb{N}; \sum_{i=a}^{b}{i} = \sum_{i=0}^{b}{i} - \sum_{i=0}^{a-1}{i} $$

The sum of numbers from 0 to n is well known

$$ \sum_{i=0}^{n}{i} = \frac{n^2+n}{2} $$

So we can use this equation to derive

$$ \sum_{i=a}^{b}{i} = \frac{b^2+b}{2} - \frac{(a-1)^2 + a - 1}{2} $$

$$ = \frac{b^2+b}{2} - \frac{a^2 - 2a + 1 + a - 1}{2} = \frac{b^2+b}{2} - \frac{a^2 - a}{2} $$

$$ = \frac{b^2+b - a^2 + a}{2} $$

This is only a couple of lines of code now, and should run in constant time.

int a = (int)Math.Ceiling((double)start_range / 15);
int b = (int)Math.Floor((double)end_range / 15);
int sum = 15 * (b*b + b - a*a + a) / 2;

Final remarks, in many languages integer division will floor the result (once the numbers are both positive). This means we can avoid Math.Floor if we assume end_range >= 0 (which seems like a fair assumption).

We also have the constant 15 strewn around the code, let's make it a variable.

int num = 15;  // A magic number specific to our problem
int a = (int)Math.Ceiling((double)start_range / num);
int b = end_range / num;
int sum = num * (b*b + b - a*a + a) / 2;

We could also avoid the Math.Ceiling call but the code may lose it's readability. The code also doesn't account for bugs like overflow, and it could be reworked to delay those issues. Currently, I don't think either of these changes would be worth it.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ @vijaypratap No problem, is there anything this is unclear in the answer? \$\endgroup\$ – spyr03 Aug 24 '18 at 12:50
  • \$\begingroup\$ No, Every thing Is clear now ;) \$\endgroup\$ – vijay pratap Aug 24 '18 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.