At first I apologize for bringing this off topic matter here. I heard of this website about one and a half year ago and I immediately fell in love with it. At first I tried to dive in with my programming knowledge and soon it drove me crazy as I failed in solving almost every problem except the simple arithmetic ones like the one mentioned here. The I finally figured out that these problems can't be solved with just developing algorithm without sufficient mathematical knowledge and of course without seeing the problem in a different angle. Let me explain.
Find the sum of all the multiples of 3 or 5 below 1000.
Of course we can use the modulo for each number below 1000 to determine which are divisible by 3 and 5. But isn't it a brute attack on these numbers? Why don't think it in a different way?
- We need to get all the numbers below 1000 those are divisible by 3
- We need to get all the numbers below 1000 those are divisible by 5
- There will be repetition of numbers as there are a lot of numbers which are divisible by both 3 and 5.
In our high school there we must be taught something called
Ven diagram. Honestly I didn't took it seriously. But later I found this ugly frightening figure has its own beauty and is very useful solving problems that are very complicated in first sight, like this problem.
You can see there are two circles A and B and they are overlapping with each other. In our problem we have two sets of numbers- those are divisible by 3 and those are divisible by 5. See these two sets have a common or intersecting set- those are divisible by both 3 and 5 (or 15 to be precise). Now the questing arises how would we get all those unique numbers from set A and B? Thats pretty simple as you might already understand. That is
A union B, pretty simple, right? This expression takes care of all repetitive elements in those sets and produces a set with unique elements form both sets. Now how do we get
A union B? The formula is-
A union B =
A intersect B
That means we need to subtract the set of numbers those are divisible by both 3 and 5.
Lets find out which numbers belong to these sets-
A intersect B
We have set our limit to 1000. Lets get the numbers those are divisible by 3 in the first place.
3, 6, 9, 12, 15, 18, 21, ..... 999
Lets take 3 common from them-
3( 1, 2, 3, 4, 5, 6, 7, ... 333 )
Can you see it? its just a simple linear arithmetic progression. Lets do the same for 5.
5, 10, 15, 20, 25, 30, 35, 40, ... 1000
5( 1, 2, 3, 4, 5, 6, 7, 8, ... 200 )
Again another linear arithmetic progression.
For 15 (divisible by both 3 and 5)
15, 30, 45, 60, 75, ... 990
15( 1, 2, 3, 4, 5, 6, ... 66 )
We need to take their summations-
1/2 * n(n+1) this is the formula for getting the some of a linear arithmetic progression, n is total number of elements in the series.
A = [ 1/2 * 333 * (333+1) ] * 3 = 166833
B = [ 1/2 * 200 * (200+1) ] * 5 = 100500
A intersect B = [ 1/2 * 66 * (66+1) ] * 15 = 33165
A union B =
A intersect B
= 166833 + 100500 - 33165 = 234168
This would be the finishing of the discussing. But WAIT as I mentioned earlier I have solved this problem and that solution is not matched with this one!! WHY !!
Finally I figured I out, this is the result of not reading the question properly.
They asked for the number below
1000, but what I have done here? for
15 it was okay, but for
5? 1000 is divisible by 5! We can't include it in the set!!
So the actual summation would be
1000 less than what we got here.
People might argue why I have posted the whole solution here. But thing is that, anyone with a little knowledge of programming and the basic understanding of modulo can solve this problem like the questioner. Is this the right way of solving these problems? Was it the intention behind developing this problem bank? Of course not, at least I believe. They certainly want us to look at problems in a different angle. Look things those are hidden in the plain sight. Sketch the idea before painting actually.
This post is for future reference only, intended to them those are interested solving the problems in this website. But also for others to show there could be some other perspective to any problem.
Thanks for reading.
As per suggestion by @200_success I am rewording here.
As per the original question I agree with @Simon André Forsberg there is certainly nothing wrong with the modulo operation. And also it can be broke down to a simpler version
A || B as he already mentioned.
I want to add with it that the condition writing is very easy with the basic understanding of
Digital Logic. I am just breaking down the idea.
In digital logic design
|| is represented as
&& is as
* (and there are some more). So the condition becomes
A + B + AB. Now you can have
AB as many times as you like as its just an
OR operation, so we can rewrite
A + B + AB
= A + AB + B + AB
= A(1+B) + B(1+A)
OR anything with a
true then the result will always be
(1+B) = 1 and
(1+A) = 1. So the expression will be
Using this algorithm you are not actually checking the numbers which are divisible by both 3 and 5. Still it gets you the correct answer. The reason behind is you are just traversing throw the numbers and moving forward. There is no chance of any repetition here. The accepted answer is all good :)