Google Interview Question for Software Engineer / Developers


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
}

- srcnaks February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 .

- FactFinder. February 02, 2015 | Flag
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

- srcnaks February 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain about your method? Thx!

- JY February 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
8
of 8 votes

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!

- srcnaks February 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

clever solution

- Shiv March 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is Awesome!

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

- Virupaksha Swamy October 20, 2015 | Flag
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;
   }

- w.y February 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Pumphouse February 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

sub sumDiv3or5 {
  $n = $_[0] - 1;

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

- jesuskwice February 02, 2015 | Flag Reply
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;

- Shashank February 06, 2015 | Flag Reply
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;
}

- rhe29 February 06, 2015 | Flag Reply
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);
}


}

- sriman2k February 07, 2015 | Flag Reply
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);

- Mr Peru February 07, 2015 | Flag Reply
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[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);

	}

}

- anuja banekar February 11, 2015 | Flag Reply
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)

- chetan February 11, 2015 | Flag Reply
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;
	}
}

- Rahul Khanna February 15, 2015 | Flag Reply
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

- liwzhi February 26, 2015 | Flag Reply
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;

- Anonymous March 01, 2015 | Flag Reply
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;
}

- Eason March 05, 2015 | Flag Reply
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;
}

- waller April 15, 2015 | Flag Reply
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.

- faru.5375 April 20, 2015 | Flag Reply
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;
}

- faru.5375 April 20, 2015 | Flag Reply
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

- hnvasa November 01, 2015 | Flag Reply
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

- Sai February 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- biolxj12 February 20, 2015 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More