Google Interview Question
Software Engineer / DevelopersCountry: -
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