Write Code vs. Write Poetry: ThreeAndFive (Math)
Question: write an algorithm to find sum of numbers which are smaller than N and divisible by 3 or 5
Example:
N = 9 => 3 + 5 + 6 = 14
N = 10 => 3 + 5 + 6 + 9 = 23
Idea: Arithmetic progression and inclusion-exclusion principle.
The sum of 3's and 5's = The sum of 3's+ The sum of 5's - The sum of 15's. Take care the question asks for smaller than, so 9 does not count if the input is 9.
Time: O(1) Space: O(1)
Question: write an algorithm to find sum of numbers which are smaller than N and divisible by 3 or 5
Example:
N = 9 => 3 + 5 + 6 = 14
N = 10 => 3 + 5 + 6 + 9 = 23
Idea: Arithmetic progression and inclusion-exclusion principle.
The sum of 3's and 5's = The sum of 3's+ The sum of 5's - The sum of 15's. Take care the question asks for smaller than, so 9 does not count if the input is 9.
Time: O(1) Space: O(1)
public int threeAndFive(int n)
{
n--;
int numOf3=n/3;
int numOf5=n/5;
int numOf15=n/15;
return getSum(0,numOf3*3,3)+getSum(0,numOf5*5,5)-getSum(0,numOf15*15,15);
}
public int getSum(int first,int last,int step)
{
int howMany=(last-first)/step+1;
int sum=(first+last)*howMany/2;
return sum;
} 