## Google Interview Question for Software Engineer / Developers

• 6

Country: -
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
21
of 21 vote

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:

``````public int SumOfNumber(int N){
N--;
int divisibleBy3 = N/3;
divisibleBy3 = (divisibleBy3 * (divisibleBy3 + 1) /2)*3;

int divisibleBy5 = N/5;
divisibleBy5 = (divisibleBy5 * (divisibleBy5 + 1) /2)*5;

int divisibleBy15 = N/15;
divisibleBy15 = (divisibleBy15 * (divisibleBy15 + 1) /2)*15;

return divisibleBy3 + divisibleBy5 - divisibleBy15
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
8

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!

Comment hidden because of low score. Click to expand.
0

clever solution

Comment hidden because of low score. Click to expand.
0

This is Awesome!

I was thinking of using a minimum heap data structure to solve this. :/

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0

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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````sub sumDiv3or5 {
\$n = \$_ - 1;

\$sum = 0;
while ( \$n > 0 ) {
if ( \$n%3 == 0 || \$n%5 == 0) {
\$sum = \$sum + \$n;
}
\$n--;
}
return \$sum;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

i=2,s=0;
while(i<N)
{
if(i%3==0||i%5==0)
s=s+i;
i++;
}
return s;

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Sum {

public static void main(String[] args) {
// TODO Auto-generated method stub

// int n = Integer.parseInt(args);
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);

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Find arithmetic progression that will run upto n-1 and then use arithmetic progression formula to find individual sum.
n1 = (n-1)/3 and n2 = (n-1)/5
n3 = (n-1)/15
sum1 = 3 + (n1-1) * 3;
sum2 = 5 + (n2-1) * 5
sum3 = 15 + (n3-1) * 15
return (sum1 + sum2 - sum3)

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution :-

``````public static void main(String[] args) {
int sum = getSum(10);
System.out.println("Sum = "+sum);
}

private static int getSum(int n) {
int sum = 0;
for (int i = 1; i < n; i++) {
if (i % 3 == 0 || i % 5 == 0) {
sum += i;
}
}
return sum;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def divide35(self,N):
output = 0
for i in range(N):
if (i%3==0 or i%5==0):
output +=i
return output``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````public static int sum(int n){
int n3 = (((n-1)/3)*(((n-1)/3) +1)/2)*3;
int n5 = (((n-1)/5)*(((n-1)/5) +1)/2)*5;
int n15 = (((n-1)/15)*(((n-1)/15) +1)/2)*15;
return n3 + n5 - n15;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <bits/stdc++.h>
using namespace std;

int f(int n, int x) {
int t = n / x;
//x 2x 3x .. tx
return (x + t*x) * t / 2;
}

int main() {
int n;
cin >> n;
n = n - 1;
printf("%d\n", f(n, 3) + f(n, 5) - f(n, 15));
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is the 1st question from ProjectEuler.net, if I remember correctly.

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
int i,c=0,t,n,*a,k;
scanf("%d",&t);
for(i=0;i<t;i++)
scanf("%d\n",a+i);

for(k=0;k<t;k++)
{
for(i=1;i<*(a+k);i++)
{
if(i%3==0 || i%5==0)
c+=i;
}
printf("%d\n",c);
c=0;
}
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def sum(target):
sum = 0
for i in range(target):
if i%3 == 0 or i%5 == 0:
sum = sum + i
else:
continue
return sum``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``return ((((N-1)/3)*((N-1)/3+1))/2)*3 + ((((N-1)/5)*((N-1)/5+1))/2)*5``

Comment hidden because of low score. Click to expand.
0

``````// idea2: O(1). NOTE: need to subtract 15
public static int sum2 (int N) {
int n3 = ((((N-1)/3)*((N-1)/3+1))/2)*3;
int n5 = ((((N-1)/5)*((N-1)/5+1))/2)*5;
int n15 = ((((N-1)/15)*((N-1)/15+1))/2)*15;
return n3+n5-n15;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.