Home | Techie Talk | Story Time | About | Contact

Thursday, January 07, 2010

a programming puzzle


 
 
Yesterday afternoon one of my friends came up with this programming puzzle:
To write an algorithm with the minimum no. of executions to calculate the Sum of all natural numbers from 1 to N, that are divisible by 4 or 7 ?
Though the question looked very simple, it was really exciting to find the solution. Here is the pseudo code of what we think as a good solution :
  1. Initialize a=0, b=0, c=0, result=0
  2. Run a loop for i = 1 to (N/28)
  3. a = a + i
  4. Next value of i
  5. Run a loop for i = (N/28)+1 to (N/7)
  6. b = b + i
  7. Next value of i
  8. Run a loop for i = (N/7)+1 to (N/4)
  9. c = c + i
  10. Next value of i
  11. result = (4*(a+b+c)) + (7*(a+b)) - (28*a)
I know there are many other smart solutions for this problem. If you, have one share it in the comments section.

Labels: ,

4 Comments:

Blogger D'pak M said...

gud one... trying to find te other way out than te one u specified...hmmm not even able to think... google had corrupted my mind big time!!!

9:02 PM  
Blogger Vetty Officer said...

@Dpak
Thank You!!!
I ll try to post more in the future to get your mind, back to form :-)

9:30 PM  
Blogger D'pak M said...

Just remembered today to solve this
1. Initialize sum=0;i and n;
2. get the value of n;
3. Run a loop from 4 to n;
4. check if value of (i mod 4=0) or (i mod 7=0)
5. sum=sum+i;
6. print sum

6:58 AM  
Blogger Vetty Officer said...

@Dpak
Simple and very clean!!!
We at first, did something similar to this and then thought the iteration in our algorithm runs N/4 times

3:44 AM  

Post a Comment

Links to this post:

Create a Link

<< Home