## Google Interview Question

Software Engineer / Developers**Country:**-

**Interview Type:**In-Person

Let us take example of 10

div3 = 3*4/2 = 6

div 5 = 2*3/2 = 3

div15 =0

div3 + div5 - div15 = 6+3 - 0 = 9

which is wrong answer .

Yeah!! you are right, I made a mistake, I corrected it.

Now, Let us take example of 10 (10 is not included)

div3 = 3*4/2 = 6*3 = 18

div 5 = 1*2/2 = 1*5 = 5

div15 =0

div3 + div5 - div15 = 18+5 - 0 = 23

My method is based on the mathematical formula that sum of numbers in between 1 and n which is "n*(n+1)/2"

Let say N is 20

the sum of numbers less than 20 and divisible by 3 are:

3 + 6 + 9 + 12 + 15 + 18 = (1+2+3+4+5+6)*3

In this case, I can calculate the sum of numbers in between 1 and 6 by using "n*(n+1)/2". So this is equals to (6*7/2) * 3

This is the same for the sum of numbers less than 20 and divisible by 5.

5 + 10 + 15 = (1+2+3)*5 => (3*4/2)*5

As seen, we add 15 in both of operations, so we have to eliminate duplicates.

In order to do that, I calculate the same for the sum of numbers less than 20 and divisible by 15.

At the end, I add the sum of divisible by 3 and the sum of divisible by 5 than subtract the sum of divisible by 15

That's it!

```
int getSumOfNums(int n)
{
int m3 = 3;
int m5 = 5;
int S = 0;
while (m3 <= n)
{
S += m3;
m3 += 3;
}
while (m5 <= n)
{
S += m5;
m5 += 5;
}
return S;
}
```

I believe you are counting numbers that are both divisible by 3 and 5 twice

```
class SumThree{
public static void main(String [] args){
System.out.println(sumThreeFive(9));
System.out.println(sumThreeFive(10));
}
static int sumThreeFive(int n){
int result = 0;
for(int x = 0; x < n; x += 3){
result += x;
}
for(int x = 0; x < n; x += 5){
if( x % 3 != 0){
result += x;
}
}
return result;
}
}
```

Recursively :

```
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <set>
using namespace std;
int smallerThanN(int N, int sum){
if(N == 0){
return sum;
}
if(N % 3 == 0 || N % 5 == 0){
sum+=N;
}
return smallerThanN(N-1, sum);
}
int main() {
int N;
cin>>N;
cout<<smallerThanN(N-1, 0)<<endl;
return 0;
}
```

package com.general;

public class FindSmallestDivisableNumberSum {

//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

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

FindSmallestDivisableNumberSum findsum=new FindSmallestDivisableNumberSum();

System.out.println("Total :::"+findsum.sum(11-1));

}

int sum(int n)

{

int sum=0;

if(n<=0)

{

return 0;

}

if(n%3==0 || n%5==0)

{

sum=sum+n;

n--;

}

else

{

n--;

}

return sum+sum(n);

}

}

function func (N) {

var divThree = 3;

var divFive = 5;

var sum = 0;

for (var i=1; i<N; i++) {

divThree--;

divFive--;

if (divThree === 0 || divFive === 0) {

sum += i;

divThree = divThree === 0? 3 : divThree;

divFive = divFive === 0? 5: divFive;

}

}

return sum;

}

var sum = func(10);

console.log(sum);

```
public class Sum {
public static void main(String[] args) {
// TODO Auto-generated method stub
// int n = Integer.parseInt(args[0]);
int n = 10;
int sum = 0;
for (int i = 1; i < n; i++) {
if ((i % 3 == 0 || i % 5 == 0)) {
sum = sum + i;
System.out.println("" + i);
}
if (sum == n) {
break;
}
}
System.out.println("" + sum);
}
}
```

my solution:

```
#include <iostream>
using namespace std;
int min(int a, int b) {
return a < b ? a : b;
}
int main() {
int N;
cin >> N;
int t = 0;
int sum = 0;
int idx3 = 1, idx5 = 1;
while (true) {
t = min(3*idx3, 5*idx5);
if (t < 3 * idx3) {
++idx5;
} else if (t < 5 * idx5) {
++idx3;
} else {
++idx3;
++idx5;
}
if (t < N) {
sum += t;
} else {
break;
}
}
cout << sum << endl;
return 0;
}
```

Firstly, I solved it by designing O(N) algorithm but than, by the help of interviewer, I came up with a solution that solves the problem in O(1)

My final solution is as follows:

- srcnaks February 02, 2015