Microsoft Interview Question Software Engineer / Developers
Assuming only the prime factors are to be 3,5,7::
for k = 1 P1 105
now go on multiplying with 3 then 5 and then 7.
k = 2 prod P2 = P1*3
k = 3 prod P3 = P1*5
k = 4 prod P4 = P1*7
k = 5 prod P5 = P2*3
k = 6 prod P6 = P2*5
k = 7 prod P7 = P2*7
Keep on growing the list to get Pk.
Also, Pk gives P(3k-1), P(3k) and P(3k+1)
So for any Kth multiple u need to generate only the factors needed for it.
This shud work:
int factor_3_5_7(int k)
{
if(k == 1)
return 3*5*7;
switch(k%3)
{
case 0:
return 5*factor_3_5_7(k/3);
case 1:
return 7*factor_3_5_7(k/3);
case 2:
return 3*factor_3_5_7((k/3) + 1);
}
}
One more thought. 105*3 < 105*5. so why not we continuously multiply the numbers by 3 instead of 3,5,7 incrementally?
U r right in saying that 105*3<105*5
but if we go on multiplying with 3 only the next number would be 105*3*3 which is 105*9(>105*5).
The sequence is 0, 3, 5, 7, 9, 15, 21, 25, 27, 35, ...
The number should be divisible by 3 OR 5 OR 7.
right, but you've misseed 14, i.e.,
it should be 3,5,6,7,9,10,12,14,15,18,20,21..
SOLUTION: maintain 3 counters for numbers divisible by 3, 5 or 7 respectively, at each iteration increment the one having minimal value, also sift out duplicates, i.e., 15 (which is divisible by 3 and 5 at the same time).
pseudocode:
int next_kth(int k) {
// maintain counters for numbers divisible by 3 OR 5 OR 7
int n3 = 3, n5 = 5, n7 = 7;
int i = 1, prev = 3;
while(i < k) {
int *pmin = &n3, inc = 3;
if(n5 < n3) {
pmin = &n5, inc = 5;
}
if(n7 < *pmin) {
pmin = &n7, inc = 7;
}
// skip the one divisible by two or more factors at the same time
if(*pmin != prev) {
i++;
}
prev = *pmin;
*pmin += inc;
}
return prev;
}
I think the approach works well even if the number shud have factors 3 or 5 or 7 and not 3,5,and 7. Only change needed is to make the first number as 3 and not 3*5*7
dont confuse ...
check approach 1, its TOTALLY WRONG, even with the change you suggested ... please see that the series is like this
3 5 6 7 9 10 12 14 ..... tb is right.
Its like a merge of the multiples of 3. 5 and 7. If we had only multiples of 3, then kth number is 3*k.
--take d 1st number
--divide it by 2...if remainder=0,go for next no
--else divide no by 3 till remainder=0, manitain a count of how many times it was divided by 3
--repeat the same with 5 and 7.
--if after dividing with all these, remainder is zero..it means it is divisible only by 3,5 & 7(if count is atleast one for each three)
--if nonzero remainder exists..it is not the required no.go to next
How do you interpret "the only factors of these numbers should be 3,5 and 7" in the problem statement to get "3 5 6 7 9 10 12 14 .."? 6 has factor 2 and 3, which contradicts with it.
I guess the original question itself is misleading. But ameya's should work, though its like brute force since there are lots of comparisions but still it will be o(k) where k is the kth number reqd
/*Design an algorithm to find the kth number divisible by only 3 or 5 or 7
i.e the only factors of these numbers should be 3,5 and 7.*/
#include<stdio.h>
#include<stdlib.h>
#define MAX_INT 50
void findKthNum(){
int shudPrint=1;
int i=1;
int num=1;
while(num<MAX_INT){
shudPrint=1;
for(i=1;i<=num;i++)
{
if(i==5||i==7||i==3){
if(num%i==0)
shudPrint*=-1;
}
else
shudPrint*=1;
}
if(shudPrint<0){
printf("\n The number is %d",num);
}
num++;
}
return;
}
int main()
{
findKthNum();
return(0);
}
/*
The number is 3
The number is 5
The number is 6
The number is 7
The number is 9
The number is 10
The number is 12
The number is 14
The number is 18
The number is 20
The number is 24
The number is 25
The number is 27
The number is 28
The number is 33
The number is 36
The number is 39
The number is 40
The number is 48
The number is 49
Press any key to continue . . .
*/
/*Design an algorithm to find the kth number divisible by only 3 or 5 or 7
i.e the only factors of these numbers should be 3,5 and 7.*/
#include<stdio.h>
#include<stdlib.h>
#define MAX_INT 50
void findKthNum(){
int shudPrint=1;
int i=1;
int num=1;
while(num<MAX_INT){
shudPrint=1;
for(i=1;i<=num;i++)
{
if(i==5||i==7||i==3){
if(num%i==0)
shudPrint*=-1;
}
else
shudPrint*=1;
}
if(shudPrint<0){
printf("\n The number is %d",num);
}
num++;
}
return;
}
int main()
{
findKthNum();
return(0);
}
/*Design an algorithm to find the kth number divisible by only 3 or 5 or 7
i.e the only factors of these numbers should be 3,5 and 7.*/
#include<stdio.h>
#include<stdlib.h>
void fact(int limit){
int isfact=0,doNotPrint=0;
int num=0,i=0;
while(num<limit){
isfact=0;
doNotPrint=0;
for(i=2;i<=num;i++){
if((num%3)==0){
isfact=1;
}
if((num%5)==0){
isfact=1;
}
if((num%7)==0){
isfact=1;
}
if(i!=3&&i!=5&&i!=7){
if((num!=i)&&(num%i)==0)
doNotPrint=1;
}
}
if(isfact==1&&doNotPrint!=1){
printf("%d \t",num);
}
num++;
}
}
void main()
{
fact(100);
}
here comes my colution
P1= 105
P2= p1*3
P3= p1*5
P4= p1*7
P5= p1*3*3 = p2*3
P6= p1*3*5 = p3*3
P7= p1*3*7 = p4*3
p8= p5*3
P9= p5*5 = (P1*3*3)*5 =(p1*3*5)*3= p6*3
p10=P5*7 = p7*3
This leads to recusion
p(k) = p(k-3)*3 for k > 4
int findkth(int k)
{
if (k == 1)
{
retrun 3*5*7;
}else if( k == 2)
{
return 3*5*7*3;
}
else if( k == 3)
{
return 3*5*7*5;
}
else if (k == 4)
return 3*5*7*7;
else if
findkth(k-3)*3;
}
Ok , again amit's solution is wrong, i dont know what this 105 assumption is .. anyways i am talking about the series 3,5,6,7 ...
Lakshmi's solution is fine, but not optimal , since its quadratic time complexity. Its brute force, though the solution is right.
It can be made closer to linear by doing this (made some modifications to lakshmi's sol to reduce time complexity)
void findKthNum() {
int shudPrint = 1;
int i = 1;
int num = 1;
while (num < 200) {
shudPrint = 1;
for (i = 3; i <= 7; i+=2) {
if (num % i == 0)
{
shudPrint = -1;
break;
}
}
if (shudPrint < 0) {
System.out.println("\n The number is "
+num);
}
num++;
}
return;
}
Either I didn't get the question right or something... if its about generating a list of numbers that are factors of 3, 5 and 7 the will the folloiwng not do?
for (int x=3;x<MAX;x++)
if (x%3==0|| x%5==0|| x%7==0)
System.out.println(x);
This snippet will generate a list as follows:
3, 5, 6, 7, 9, 10, 12, 14, 15, 18, 20, 21, 24, 25, 27, 28, 30, 33, 35, 36, 39, 40, 42, 45, 48, 49 etc..
The sample above are missing numbers like 14, 30 etc...
I can't see the point of writing any more lines than that!
I'll be happy to be corrected.
Cheers!
J
The Algorithm will be-
If addition of all digit is divisible by 3, then no. is divisible by 3. If last digit is 5 or 0, the no. is divisible by 5 and for 7, if you double the last digit and subtract it from rest of the number, and if it gives ans 0 then its divisible by 7 or again repeat the step.
My solution to this is:
assuming that 3,5,7,9,15,21,25, 27, 35 is the sequence that should be printed... then
1) check if divisible by 3 using mod operation. If divisible then get the quotient. Then take the quotient and apply log to the base 3, log to the base 5 and log to the base 7. If any of the logs return a exact integer, that number is valid....
Do the similar step for 5 and 7 ie checking divisibility, get quotient and applying logs....
This should give us the required sequence
only factors are 3,5,7, so could not be 2,4,6,8,9
shoud be in the format of (2n+1)*3*(5^k)*(7^L)*(3m+1) or (2n+1)*3*(5^k)*(7^L)*(3m+2), where n>=0,m>=0.
2n+1 makes sure that only odd numbers are produced. 3 is a factor but not 9 thus 3*(3m+1) or 3*(3m+2), 5 and 7 are factors so that (5^k) and (7^L), where m,n,k,L>=0.
using the above formula and do a loop till count==k.
void print_3_5_7(int k)
{
int count=0;
int i=0;
int j=0;
int s=0;
int t=0;
int flag=1;
float f5=5;
float f7=7;
while(count<=k)
{
count++;
printf("%d th number is %d",count,(2*i+1)*3*(3*j+1)*pow(f5,s)*pow(f7,5));
count++;
printf("%d th number is %d",count,(2*i+1)*3*(3*j+2)*pow(f5,s)*pow(f7,5));
if(flag==1)
{
i++;
flag=2; //increase i first only
}
if(flag==2)
{
i=j++;
flag==3;//secondly increase j only
}
if(flag==3)
{
j=s++;
flag=4;//thirdly increase s only
}
if(flag=4)
{
s=t++;
flag=1;//fourthly increase t only
}
}
}
IsValid and DoIsValid are used to check whether the number is valid. and then, my function just to need to check the number from 1 to MaxNumber and print valid number;
bool DoIsValid(int number)
{
if (number%3==0)return DoIsValid(number/3);
else if (number%5==0)return DoIsValid(number/5);
else if (number%7==0)return DoIsValid(number/7);
else if (number == 1) return true;
else return false;
};
bool IsValid(int number)
{
if (number > 1)return DoIsValid(number);
else return false;
};
void GetFactors(int maxNumber)
{
int kth = 0;
for (int i=0;i<maxNumber;i++)
{
if (IsValid(i))
{
++kth;
cout<<kth<<"th : "<<i<<endl;
}
}
};
here's output
1th : 3
2th : 5
3th : 7
4th : 9
5th : 15
6th : 21
7th : 25
8th : 27
9th : 35
10th : 45
11th : 49
12th : 63
13th : 75
14th : 81
int kth(int k)
{
int three = 0;
int five = 0;
int seven = 0;
vector<int> s(k+1);
s[0] = 1;
for(int i = 1; i <= k; i++)
{
int a = 3*s[three];
int b = 5*s[five];
int c = 7*s[seven];
if(a <= b && a <= c)
{
s[i] = a;
if(a == b)
five++;
if(a == c)
seven++;
three++;
}
else if(b <= c)
{
s[i] = b;
if(b == c)
seven++;
five++;
}
else
{
s[i] = c;
seven++;
}
}
return s[k];
}
If at all the number if of the form (3**i)*(5**j)*(7**k), the solution is already discussed by varun1425. It looks good to me.
But, if the condition that numbers should be strictly divisible by 3 or 5 or 7.. then i think the sequence is something like,
3, 5, 7, 15, 21, 35, 105 <End of sequence> [Assuming the number can be divisible by combination of {3,5,7}] OR
if 'OR' is strict, then i guess numbers should be {3,5,7}
Primarily the problem statement indicates that the number should be a factor of 3,5,7 NOT 2. So all solutions printing out numbers like 6,14,etc are wrong.
N = 3^x * 5^y * 7^z
The code is
void findKthNumber(int k)
{
map<int,int> myMap;
queue<int> q;
int ctr=0;
q.push(1);
while(ctr < k)
{
int num = q.front();
q.pop();
if(myMap[num*3] != 1)
{
q.push(num*3);
myMap[num*3] = 1;
if(++ctr == k)
{
cout<<num*3<<endl;
return;
}
}
if(myMap[num*5] != 1)
{
q.push(num*5);
myMap[num*5] = 1;
if(++ctr == k)
{
cout<<num*5<<endl;
return;
}
}
if(myMap[num*7] != 1)
{
q.push(num*7);
myMap[num*7] = 1;
if(++ctr == k)
{
cout<<num*7<<endl;
return;
}
}
}
}
for k=1, the answer from the question is 3, k=2 it is 5 and so on...
All we need to do is to create a max heap (initially created by BFS traversal of a tree with three childred for multiplication with 3, 5 and 7). Once K elements are filled up, we extract the max element and continue with the BFS, we stop considering values which are greater than the current Kth max value. If we find a value less than this max, we remove the max element and insert this element into the heap after which we find the maximum again. Continue till all elements in the BFS stack are greater than the current max
I don't think we should list every 1st, 2nd, until Kth with brutal force.
My thinking is like this:
1) We should know the position of 7, 7*7, 7*7*7, ..., with mathematics;
2) For K, we should know it's between 7^(n-1) and 7^(n);
3) Within this limited range, we can recursively know what exactly is on the Kth position.
I have to confess I'm having trouble to get the positions of all the 7^i
We can design an algorithm to sort Value(n,m,p) = 3^n * 5^m * 7^p (n,m，P=1..k).
My algorithm is to list all values between Value(0, 0, 0) and Value(1,1,1) to a table.
The pattern of (n, m, p) will repeat.
n m p value
Table[1] 0 0 0 1
Table[2] 1 0 0 3
Table[3] 0 1 0 5
Table[4] 0 0 1 7
Table[5] 2 0 0 9
Table[6] 1 1 0 15
Table[7] 1 0 1 21
Table[8] 0 2 0 25
Table[9] 3 0 0 27
Table[10] 0 1 1 35
Table[11] 2 1 0 45
Table[12] 0 0 2 49
Table[13] 4 0 0 81
-------------------------------------------
Table[14] 1 1 1 105
The 14th number is
V(n, m, p) = V[(1, 1, 1) + (0, 0, 0)] = V(1,1,1)
The 15th number is
V(n, m, p) = V[(1, 1, 1) + (1, 0, 0)] = V(2,1,1)
The 16th number is
V(n, m, p) = V[(1, 1, 1) + (0, 1, 0)] = V(1,2,1)
..................
The 27th number is
V(n, m, p) = V[(1, 1, 1) + (4, 0, 0)] = V(5,1,1)
The 28th number is
V(n, m, p) = V[(2, 2, 2) + (0, 0, 0)] = V(2,2,2)
The N-th number is
V(n, m, p) = V[(N/14, N/14, N/14) + Table(N%14)]
the way i look at it is 3x3,3x5,3x7.5x5,5x7,7x7 so 3,5,7,and.9.,15,21,25 35 , 49 end so far basically its numbers with no other factors than 3 or OR 5 OR 7 AND ANY COMBO OF THESE NUMBERS! AS FACTORS so u can not use 9 again as 9 becomes a factor so 3 ends at 9 but using 5 its 15 and using 7 its 21 so 105 is wrong as 35x3=105(factors 35 and 3)so the ans is write a simple algorithm that does this and gives kth number theirs only nine.
The question meant "The only PRIME factors". If you remove the word "PRIME", the only such number is 3*5*7. It is indeed obvious that the interviewer meant PRIME factors. Otherwise one could always consider the case "1" as a factor.
- Anbe September 16, 2008