Jump to content
  • Advertisement
Sign in to follow this  
Shruubi

a counting problem... well... problem

This topic is 2544 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

so, i've discovered projecteuler.net. however, i'm stuck on the first problem.

now, it isn't the actual solving of the problem itself, i already have my algorithm to solve it, however, i think there is a problem in my algorithms logic.

the question is as follows:


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.

[/quote]

and my c++ program to solve it is:


#include <iostream>
#include <math.h>

using namespace std;

int main()
{
int answer = 0;

for (int number = 0; number < 1000; number++)
{
if ((number%3) || (number%5) == 0)
{
if ((number%3) && (number%5) == 0)
{
answer += 0;
}
else
{
answer += number;
}
}
}

cout << answer <<endl;
return 0;
}


when i change the run until clause in the for statement to 10 so i can check my working out against the correct solution however, it outputs 22 instead of 23, and i just can't figure out why this is.

any help at all would be much appreciated as i've looked at this problem from every which way and cannot see the error.


Share this post


Link to post
Share on other sites
Advertisement
Hi there,

in the initial if-statement, you're missing a '== 0'. This way the left hand side of the condition if ((number%3) || (number%5) == 0) checks out wrong.

Warning! Spoilers and totally unproven claims ahead :)

Also, I think you can compute the numbers directly without a loop if you use the fact that the sum of the numbers {1, ..., n} equals to n*(n-1). Let f_n({a}) be the sum of the numbers from 1..n which are multiples of a: a8ac14f04613c4bee6cf6cb5c357cc87-1.gif. The <...> thing is meant to be 1 if the inside statement is true, 0 otherwise (basically the same as in your algorithm's inner-most if-statement). However, you can factor out the a: a8ac14f04613c4bee6cf6cb5c357cc87-2.gif. Now, if your interested in multiples of {a,b} instead of just {a}, you can apply the principle of inclusion-exclusion: Just using a8ac14f04613c4bee6cf6cb5c357cc87-3.gif will count multiples of both a and b twice, right? So you have to subtract these again: a8ac14f04613c4bee6cf6cb5c357cc87-4.gif. Here, the 'gcd(...)' means the greatest common divisor. You might want to use it as any number is divisible by both a and b if and only if it is divisible by gcd(a,b).


- Michael

Share this post


Link to post
Share on other sites
The problem is indeed the lack of comparison against zero.


You might want to use it as any number is divisible by both a and b if and only if it is divisible by gcd(a,b).
Except that the problem is the sum of numbers divisible by a or b, not a and b.

Logically the for-loop should start at 1, not 0, and the innermost if-statement is not needed, because you don't care if it is a multiple of both since you still do the same thing.
No need to add zero to 'answer' either.

Share this post


Link to post
Share on other sites

The problem is indeed the lack of comparison against zero.

[quote name='Michael N.' timestamp='1307253228' post='4819645']
You might want to use it as any number is divisible by both a and b if and only if it is divisible by gcd(a,b).
Except that the problem is the sum of numbers divisible by a or b, not a and b.

Logically the for-loop should start at 1, not 0, and the innermost if-statement is not needed, because you don't care if it is a multiple of both since you still do the same thing.
No need to add zero to 'answer' either.
[/quote]

the innermost if was kind of my attempt at doing an exclusive or statement, i think i can condense it into one if statement.

thank you, i didn't include the other check if it is equal to 0 because i didn't realize it was necessary. obviously i was mistaken.

re-edit: i removed the middle if statement and it worked. although i'm a little confused as to why, the logical OR statement is an inclusive OR correct? if that's the case, then wouldn't it count doubles? i was under the impression i needed to use exclusive OR statements to get the correct answer.

Share this post


Link to post
Share on other sites
I think you should loop through multiples of 5 and add if below 1000 and then rhe same with multiples of 3 UNLESS its dividable by 5 in wich case you have already added it

Share this post


Link to post
Share on other sites

re-edit: i removed the middle if statement and it worked. although i'm a little confused as to why, the logical OR statement is an inclusive OR correct? if that's the case, then wouldn't it count doubles? i was under the impression i needed to use exclusive OR statements to get the correct answer.

Multiples of both 3 and 5 won't be counted twice. You only loop through each number once, and your logic does not allow for it to be counted twice in one loop iteration.

Share this post


Link to post
Share on other sites

I think you should loop through multiples of 5 and add if below 1000 and then rhe same with multiples of 3 UNLESS its dividable by 5 in wich case you have already added it


you could, and that is a perfectly valid solution, however, in terms of optimising the program, this would not be advised.


[quote name='Shruubi' timestamp='1307270515' post='4819699']
re-edit: i removed the middle if statement and it worked. although i'm a little confused as to why, the logical OR statement is an inclusive OR correct? if that's the case, then wouldn't it count doubles? i was under the impression i needed to use exclusive OR statements to get the correct answer.

Multiples of both 3 and 5 won't be counted twice. You only loop through each number once, and your logic does not allow for it to be counted twice in one loop iteration.
[/quote]

thank you for that clarification, i think i put my mind in a state where i was looking for a more complex solution than was needed.

Share this post


Link to post
Share on other sites

Except that the problem is the sum of numbers divisible by a or b, not a and b.



True, but the subtraction involving the gcd is only there as my method counts multiples of 'a' and 'b' independently. Therefore, something like 15 would be counted twice when adding up all the multiples of 3 or 5. I see nothing wrong with that...

Very simple example: Add up all the numbers from 1 to N which are multiples of 3 or multiples of 3. Then you immediately see why you need the subtraction in a8ac14f04613c4bee6cf6cb5c357cc87-4.gif. Since gcd(3,3)=3 this quickly simplifies to f_n({3,3})=f_n({3}). In general, however, this overcounting has to be handled (Although, as it was pointed out, the OP's algorithm doesn't do this).

- Michael.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!