Amazon Interview Question
Software Engineer / DevelopersTeam: logistics
Country: United States
Interview Type: In-Person
this code is giving 11th Ugly number as 14 but . 2*7 can not be an Ugly number according to 2^x * 2^y * 2^z.
You are right Maddy, I did for multiples and not prime factors. I`m adjusting the code. Please let me know if you find any issues. Sorry about that.
Why do u think there is a "wording problem"? If it was, they would not provide us "1" and "itself" as dividers. This means that Nth "ugly number" either Nth number in natural row (1, 2, 3...etc) OR 30*N.
I can't find other meanings in the task.
Not really. It means that those are numbers compose only by the prime factors of 2, 3 and 5. Attention to 1 which is 2^0 + 3^0 + 5^0. So they are only divisible by 1, 2, 3, 5 and itself. This is a known problem and it is one of the problems addressed by the book Cracking the Code Interview, whose author is the CEO of CareerCup. Do a quick search on the web and you should find references to this problem.
import logging
def getNthUglyNumber(n):
counter =0
numbersTotest = 0
while counter<n:
numbersTotest +=1
def divideFull(dividend,divider):
while dividend%divider==0:
dividend = dividend/divider
return dividend
num = divideFull(numbersTotest,2)
num = divideFull(num,3)
num = divideFull(num,5)
if num==1:
counter +=1
print counter,numbersTotest
print getNthUglyNumber(10)
1. anything which can be fully divided by 1,2,3,5 and itself will be fully divided by 5*3*2 = 30. So the above operation can be changed dividerFull(num, 30) exception is 0
2. instead of using the while loop, get the dividend and then just put the condition num%(dividend*30)==0
Ugly numbers are numbers that can be divided by 1 OR 2 OR 3 OR 5, the wording of the problem is wrong. This can be solved with dynamic programming by creating an array of length n (where n is the nth ugly number we want to find) and generating multiples of 2, 3 and 5 until we reach n.
What is the sue case of using dynamic programming in the problem. Simply try to divide the number by 2,3 and 5 and break if in any case reminder comes as 0 ...
this will be faster than dynamic programming
Anonymous, "Ugly numbers are numbers that can be divided by 1 OR 2 OR 3 OR 5" is wrong too.
Ugly numbers are those that have prime factors of 2, 3, and 5. By this definition, 14 is not an ugly number. By your definition, it is. The solution you gave assumes the definition of prime factors I wrote above.
An issue with this code is that: it may fail (too slow) to find the 100th ugly number (input n = 100)
The wording of the problem is confusing. If you mean that 1, 2, 3, 5, and itself must divide the ugly number, it will obviously be a multiple of 60. The nth ugly number is n th natural number times 60. We don't need a program for this problem. The sequence will then be 60, 120, 180, 240, etc.
If, however, you mean a number that is divisible by one or more of {1, 2, 3, 5}, then the sequence will be 1, 2, 3, 4, 5, 6, 8, 9, 10, etc. Do you mean the second option?
This problem can be done in O(1). Here's how.
Given 1, 2, 3, or 5 as the ugly numbers, we ask how many numbers exist in block lengths of 2*3*5 = 30. That count is 22. (To see how -- there are 15 evens + 10 three multiples + 6 five multiples = 31 total. We are double counting, so remove multiples of 6, that is 5 of them, multiples of 10, which is 3 of them, and multiples of 15, which is 2 of them to give a total of 31 - (5 + 3 + 2) = 21. Now, we need to add back multiples of 30 since we removed things multiple times. That number to be added back is 1. New total: 21 + 1 = 22).
That is, 22 numbers exist for every 30 numbers.
So, you supply me an n. For example, let us say this number is below 22, I know my search space is limited to the interval [0, 30]. OTOH, if n were between 22 and 44, I know, the search space is between 30 and 40. So given any n, I need to look at interval 30*(n/22 - 1) and 30*(n/22).
The point is I need to look at only 30 numbers, no matter what n is supplied. IMO, this solution is very elegant in terms of time and space.
Comments?
If the problem says divisible by 2 and 3 and 5 ..... then it is pretty straightforward.
Th code for it is :-
import java.util.Scanner;
public class UglyNumbers {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("Enter a Number ");
int n = in.nextInt();
System.out.print("Nth number of ugly series is : "+uglyNumber(n));
}
public static int uglyNumber(int n){
/* Since the LCM of 1,2,3,5 is 30
* The smallest ugly number is 30
* and all ugly numbers would be a
* multiple of 30
*/
return 30 * n;
}
}
"ugly numbers are numbers that can only be fully divided by 1, 2, 3, 5 and itself."
I am more focus the word, "only". If the number also can be divided by others , it does not count ?
for example, 30 can be divided by 15 which is not in the list of, 1,2,3,5 and 30 ?
7 should be counted since it can be only divided by 1 and 7 which is in the list ?
we can see the problem in this way . Ugly number is the number which have factors as (1,2,3,5) only. So we can get the nth number from below series.
2^x * 3^y *5^z.
1st : x=0,y=0,z=0 : 1
2nd: 1,0,0 : 2
3rd : 0,1,0 :3
4th: 2,0,0 :4
5th: 0,0,1 :5
6th: 1,1,0 :6
7th: 3,0,0 :8
8th: 0,2,0 :9
9th: 1,0,1 :10
10th: 2,1,0: 12
11th: 0,1,1: 15
12th: 4,0,0: 16
13th: 1,2,0: 18
14th: 2,0,1: 20
15th: 3,1,0: 24
16th: 0,0,2: 25
........
Here is the solution.In the series we can see, no prime number and multiple of prime number is coming. so we can say nth ugly number is n+m.
where m is the sum of prime number count after 5 in n+m numbers and multiple of prime number after 5.
please suggest, how to improve the complexity.
Code in JAVA
public static void ugly(int n){
int i = 0;
if(n < 1)
System.out.println("Invalid Input");
else if (n > 6)
for (i=6; i<=n ;i++){
if(isPrime(i)){
n++;
}
else if(isPrimeMultiple(i))
n++;
}
System.out.println("Ugly : " + n);
}
public static boolean isPrime(int n){
if(n<=1)
return false;
for (int i = 2; i <= Math.sqrt(n); i++) {
if (n % i == 0){
return false;
}
}
return true;
}
public static boolean isPrimeMultiple(int n){
n = remove2(n);
n = remove3(n);
n = remove5(n);
return n>1;
}
public static int remove2(int n){
while(n%2==0)
n=n/2;
return n;
}
public static int remove3(int n){
while(n%3==0)
n=n/3;
return n;
}
public static int remove5(int n){
while(n%5==0)
n=n/5;
return n;
}
src: geeksofgeeks
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 150′th ugly number
public class UglyNumberNth {
public static void main(String[] args) {
nthUglyNumber(9);
}
private static void nthUglyNumber(int i) {
int count =0;
int temp = 2;
while(true){
boolean flag = false;
if(temp%2==0 || temp%3==0 || temp%5 == 0){
for (int j = 1; j <= temp/2; j++) {
if(j==1||j==2||j==3||j==5){
}else if(temp%j==0){
flag = true;
//System.out.println(temp+"-"+count +" -- "+j);
break;
}
}
if(!flag){
count++;
if(count>i){
break;
}
System.out.println("****** "+temp);
}
}
temp++;
}
}
}
static int maxDivide(int num, int divider)
{
while(num % divider == 0)
num = num / divider;
return num;
}
static bool isNumberUgly(int num)
{
if (0 == num)
return false;
return maxDivide(maxDivide(maxDivide(num, 2), 3), 5) == 1;
}
static int findNthUglyNumber(int n)
{
int num = 1;
int count = 1;
while (count < n)
{
++num;
if (isNumberUgly(num))
++count;
}
return num;
}
# 1 is the first ugly number.
# If R is an ugly number, then 2*R, 3*R and 5*R are all ugly numbers as well.
# There are many ugly numbers so we need a priority queue to select them in ascending order.
# Suppose R equals to 2^a * 3^b, should 2*R be pushed into the priority queue? Considering another number R' which equals to 2^(a+1) * 3^(b-1), we known that R' < R. So even if both of R' & R are in the priority queue, R' would be selected before R. When R' is selected, 3*R' should be pushed into priority queue at the same time. Which means 3*R' is pushed into queue before 2*R, so we do not have to push 2*R again (3*R' = 2^(a+1) * 3^b = 2*R).
# So every time when a number R is selected, new ugly number should be generated by multiply the selected number with a new factor P, and P must greater or equal to the largest prime factor of R.
# To illustrate the idea, build a tree with root node 1 (the first ugly number). All node values in this tree are their parent values multiple 2, 3, or 5 (e.g. children of 1 are 2, 3 and 5. children of 2 are 2*2, 2*3 and 2*5. etc.). Remove the duplicated numbers and selected remains in ascending order.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Generator {
priority_queue<int, vector<int>, greater<int>> pool;
Generator() {
this->pool.push(1);
}
int Next() {
int number = this->pool.top();
this->pool.pop();
if (number % 5 == 0) {
this->pool.push(number * 5);
} else if (number % 3 == 0) {
this->pool.push(number * 3);
this->pool.push(number * 5);
} else {
this->pool.push(number * 2);
this->pool.push(number * 3);
this->pool.push(number * 5);
}
return number;
}
};
int main() {
Generator g;
for (int i = 0; i < 100; ++i) {
cout << g.Next() << endl;
}
}
Is the 1 trillionth ugly number = 2^1126 * 3^16930 * 5^40 =
381432500501368203378087989364684566003196981728287861209871741226226525212721355737268953258289365867404981597404054421789109760844500952247925146099494880428508529216246244511244867744925683802530879101066553238177517252767636184594334387309922212648235124288475749806206347656448649307449094910179817154595317474803832693242133737544677246725893557633654926313190236770066360622938574559713516391564144547396432295444647508095324602670011327673727739957987675308549713969242190198751614368654552970058346461965230959479549183120034812416513902203057203906014674293111023568658682172646478061761547592733863996763247542352604485351550500259020895056662371226777511522717096663981648958925160590781203849840250387080913587872019962833628471286020944446036116227561664422800434640303596225654342128319942334560763248219521958112980122656154322288782197044471919701456432396711460047592839239991995065396986351375936676582038764364135956974830358423813236898274231178796818725438341925717416647797193232651544867460829679476323177007770129492717496915465821550889348573821649618385759888429506048769746984318779379387235508725017626931291783495454078633856251352965367975156315500138512273903936359696710772951672000764780797534135617532615069653722327470053996537987966507375483235828950483009204942019944815486836876541835728053944013919256953575734463016041957802358498736651342458150091298395471511454596373412462056385448933043835369209570333091893485364162359777824091047663292556531848442316429641804084227404418581764178118799902088490330934415783419436766111289751728080616887467259380495593993999007416205941205205648099105889610584749882260704486606343851508816670299483639904252062724303543588169194142282157474210801912915786508784824094915984977696488857697688837471802181949631171427892810191259844779496613305824486287004098713333319920755014545092234973161765100732819317337968563808224916203530649482072304780251606930250679585076842569969013704981775998788013146577781010855892536687825783816873026869460088122790746302240414681660795730017210102260941819954392050654877165897092829136349360646270693828793890131656110085555102549404684366912948435560177729319213268641684600573665767060907665495486646622569960715616755051756190976734484896258475838165360541628697955550814600563240253989152549004757785712811084127267978889840332750151081858425794804819882698588743364095268350947868326169540540927401161514106448366645429921763405608340439515742058526616878358948974369782609855655675294824544796287426791518372131265927196232745663598948967696042989478611802894904236740139363217489156764375914289396097600245602455102665784834589391013700595861674262694959296141311362268034856325830685732072966898388781459190722295245407456302472041305892463709388574440918398498912456769938061673445888390451220594643942529155114279393017006570423565313506923730210404246978328087096083105528955910796927360711527123422727091919503910519570848679688959076293500742647850023183903147481723829114314447574070129805594179742737206447355799817808476580365839278299208478092312652752038210700664065535500101795705182938559765635161132444138452049446242866671947399765832117854684941405518872019649121058590993958524773370229558868931306124971557064586217966030355901338403646166993476691398603434729560312281007995073275898516459971220715657699387523541330373102873040610222293381440297359855604813713487045065173446504818338471581488928367463848756107869477386616119827264615280682634297173123261177373540526229015339553181728486997297652385088193337393105864888294893549092590589234315492057527958083663610553788816353890227097781381357352939605796261046157741589539421216828857527824381073392141187857645455838419363948924419249789707529869828445816097149777574457846168863021576195719281270085256789215456845232276418086131573167048399735999446047308893077404474069962516873750976531134605177381860006560751623956248369842277829338354338239593657154667339823706858657828846076357564141041144132653918540614567364428999424953532960255704726380063206414477874473011744905086193323212196230461016234776009019556145289115469651975034868214875465621658690986611676250782377764355946861847552708036446068853697203543193591291479535305020014678268365390166542449626331277902891960154198320640447275407283842209433526300227914464028822306278110016143575327647214340233047351066244266576781395298905370583147237169346233738497514110562281408609355349560048891725146122806891273216369639851077436406592893753729690835960446164271693935812602839579229273571311436712152831655030039235186756793939086768598572119711208661869571225003654933600358235541115015140765308202890492006769502831942411647119268717661579552940663489637401616797752823585038415670347522491030842381108052530483847642586054403601447134420408642823870164041381659369018513999163584560593071103729523430358336622667039689019463450035988415451651556138276294562084712233906409886132878792332009910602861356452290649901406349299580539448017304889428440240802135729922126748998968758135863691971362531429661032283162834322098678183994246815437051118481713336003797985203440751253618910774614857932245930438370672346152009783488939557110237315572630011188807032434684323410978888350161084958463242054583107168129809365906510277520834199584853707564975390831892479367377747704598145178429542726047766484073513798982629254881015589607774241895593929484591210459733972089725801226712669526167643559949974875548078686724927959894386937328668387305412202357110352655277305103854151248777748003912914187166760456241514381336238622922176322074649573786643542323409287130562729156125057560479177108923976620833793789796446288379720457136250236958013583837301292182469558879831232003762891433765287723404287606949817910100748412691304937225478604543944712581388884826063975760055469108001222120792097236141905327681074374503535383573887538394160004316349174529760474207668106657055423044749824787960307145882371169230102374074351105763898972107677525315719770924516050502350592454339732826134162740274248974361445949386533845057455877594711936404651222213700068778072085053124279558647251710675496148419947187710144483465061491027072800457529151879293653843768514232911643040932812315558121776764357308509623935085751986865128160332811976103135474624261041393051559430318488475203773394340924758715006468013654729377120628769731870289123185162241978318947284851186423539183667271806058237944470875029035834532404348499800745036015383845562794552147701458176737502147741344932704133451193644858265528208740292334938649754442528229593081859268043589651263172114838672296433455437884811594947448395870528675891271525327850454305478319284798674414283610758455864692025010128412213817083204073411513858208943478155840652861722720103650369636812940260428918875534584092687774013464914555586538728185037492887768408661425559897617085879377999322482768408377153456578353192600088691156247278285376650302918020364100406696826182661984739230472483569772685421656899496425201205051292520579762192167734835433528278166901986761398474772205192235112447073768501872380291313256166658437838705840725910673067001694599268891466041051301357758142028926221241150737563383094473077416353682405442288466206749465489838345288022292312683862458722942463812695992417502575991713081094596966691251333855046350205503351216355174898522776275164001673042505352494099356428324565551222456829595241110281915073149143722112106597387867484881077143415016534201519380037945223589464410350907465343341743447452315897697439240008325903230535647680590852852742770572098939348138339728240185339597903790459538131474918499054223109084798550228061965714109171636789980604603951414783253430837758215397191494180722955449120576644783948206405282461782774370469388077935264165516109137201074028611700340924754761566309315919658543055145034524177191198831130692839923393256394546847019892233823877166696730848415975077044614276994220212117518343302008536715617994671386526822378431167884328996507773315531097327141735084258815563626491801736919645485414765901463436227902736185065138747561652147253349857191230736498725073474761761827043174919382521944349056386305186481198173455293985211104739115063577688592953395294676810655962894343645229199990527683439765973171737546615533185149900878528865499358951458942761341111026253722935261672690109408935429704509667276178562289568318381821903503360000000000000000000000000000000000000000
{Is the 1 trillionth ugly number = 2^1126 * 3^16930 * 5^40 =
381432500501368203378087989364684566003196981728287861209871741226226525212721355737268953258289365867404981597404054421789109760844500952247925146099494880428508529216246244511244867744925683802530879101066553238177517252767636184594334387309922212648235124288475749806206347656448649307449094910179817154595317474803832693242133737544677246725893557633654926313190236770066360622938574559713516391564144547396432295444647508095324602670011327673727739957987675308549713969242190198751614368654552970058346461965230959479549183120034812416513902203057203906014674293111023568658682172646478061761547592733863996763247542352604485351550500259020895056662371226777511522717096663981648958925160590781203849840250387080913587872019962833628471286020944446036116227561664422800434640303596225654342128319942334560763248219521958112980122656154322288782197044471919701456432396711460047592839239991995065396986351375936676582038764364135956974830358423813236898274231178796818725438341925717416647797193232651544867460829679476323177007770129492717496915465821550889348573821649618385759888429506048769746984318779379387235508725017626931291783495454078633856251352965367975156315500138512273903936359696710772951672000764780797534135617532615069653722327470053996537987966507375483235828950483009204942019944815486836876541835728053944013919256953575734463016041957802358498736651342458150091298395471511454596373412462056385448933043835369209570333091893485364162359777824091047663292556531848442316429641804084227404418581764178118799902088490330934415783419436766111289751728080616887467259380495593993999007416205941205205648099105889610584749882260704486606343851508816670299483639904252062724303543588169194142282157474210801912915786508784824094915984977696488857697688837471802181949631171427892810191259844779496613305824486287004098713333319920755014545092234973161765100732819317337968563808224916203530649482072304780251606930250679585076842569969013704981775998788013146577781010855892536687825783816873026869460088122790746302240414681660795730017210102260941819954392050654877165897092829136349360646270693828793890131656110085555102549404684366912948435560177729319213268641684600573665767060907665495486646622569960715616755051756190976734484896258475838165360541628697955550814600563240253989152549004757785712811084127267978889840332750151081858425794804819882698588743364095268350947868326169540540927401161514106448366645429921763405608340439515742058526616878358948974369782609855655675294824544796287426791518372131265927196232745663598948967696042989478611802894904236740139363217489156764375914289396097600245602455102665784834589391013700595861674262694959296141311362268034856325830685732072966898388781459190722295245407456302472041305892463709388574440918398498912456769938061673445888390451220594643942529155114279393017006570423565313506923730210404246978328087096083105528955910796927360711527123422727091919503910519570848679688959076293500742647850023183903147481723829114314447574070129805594179742737206447355799817808476580365839278299208478092312652752038210700664065535500101795705182938559765635161132444138452049446242866671947399765832117854684941405518872019649121058590993958524773370229558868931306124971557064586217966030355901338403646166993476691398603434729560312281007995073275898516459971220715657699387523541330373102873040610222293381440297359855604813713487045065173446504818338471581488928367463848756107869477386616119827264615280682634297173123261177373540526229015339553181728486997297652385088193337393105864888294893549092590589234315492057527958083663610553788816353890227097781381357352939605796261046157741589539421216828857527824381073392141187857645455838419363948924419249789707529869828445816097149777574457846168863021576195719281270085256789215456845232276418086131573167048399735999446047308893077404474069962516873750976531134605177381860006560751623956248369842277829338354338239593657154667339823706858657828846076357564141041144132653918540614567364428999424953532960255704726380063206414477874473011744905086193323212196230461016234776009019556145289115469651975034868214875465621658690986611676250782377764355946861847552708036446068853697203543193591291479535305020014678268365390166542449626331277902891960154198320640447275407283842209433526300227914464028822306278110016143575327647214340233047351066244266576781395298905370583147237169346233738497514110562281408609355349560048891725146122806891273216369639851077436406592893753729690835960446164271693935812602839579229273571311436712152831655030039235186756793939086768598572119711208661869571225003654933600358235541115015140765308202890492006769502831942411647119268717661579552940663489637401616797752823585038415670347522491030842381108052530483847642586054403601447134420408642823870164041381659369018513999163584560593071103729523430358336622667039689019463450035988415451651556138276294562084712233906409886132878792332009910602861356452290649901406349299580539448017304889428440240802135729922126748998968758135863691971362531429661032283162834322098678183994246815437051118481713336003797985203440751253618910774614857932245930438370672346152009783488939557110237315572630011188807032434684323410978888350161084958463242054583107168129809365906510277520834199584853707564975390831892479367377747704598145178429542726047766484073513798982629254881015589607774241895593929484591210459733972089725801226712669526167643559949974875548078686724927959894386937328668387305412202357110352655277305103854151248777748003912914187166760456241514381336238622922176322074649573786643542323409287130562729156125057560479177108923976620833793789796446288379720457136250236958013583837301292182469558879831232003762891433765287723404287606949817910100748412691304937225478604543944712581388884826063975760055469108001222120792097236141905327681074374503535383573887538394160004316349174529760474207668106657055423044749824787960307145882371169230102374074351105763898972107677525315719770924516050502350592454339732826134162740274248974361445949386533845057455877594711936404651222213700068778072085053124279558647251710675496148419947187710144483465061491027072800457529151879293653843768514232911643040932812315558121776764357308509623935085751986865128160332811976103135474624261041393051559430318488475203773394340924758715006468013654729377120628769731870289123185162241978318947284851186423539183667271806058237944470875029035834532404348499800745036015383845562794552147701458176737502147741344932704133451193644858265528208740292334938649754442528229593081859268043589651263172114838672296433455437884811594947448395870528675891271525327850454305478319284798674414283610758455864692025010128412213817083204073411513858208943478155840652861722720103650369636812940260428918875534584092687774013464914555586538728185037492887768408661425559897617085879377999322482768408377153456578353192600088691156247278285376650302918020364100406696826182661984739230472483569772685421656899496425201205051292520579762192167734835433528278166901986761398474772205192235112447073768501872380291313256166658437838705840725910673067001694599268891466041051301357758142028926221241150737563383094473077416353682405442288466206749465489838345288022292312683862458722942463812695992417502575991713081094596966691251333855046350205503351216355174898522776275164001673042505352494099356428324565551222456829595241110281915073149143722112106597387867484881077143415016534201519380037945223589464410350907465343341743447452315897697439240008325903230535647680590852852742770572098939348138339728240185339597903790459538131474918499054223109084798550228061965714109171636789980604603951414783253430837758215397191494180722955449120576644783948206405282461782774370469388077935264165516109137201074028611700340924754761566309315919658543055145034524177191198831130692839923393256394546847019892233823877166696730848415975077044614276994220212117518343302008536715617994671386526822378431167884328996507773315531097327141735084258815563626491801736919645485414765901463436227902736185065138747561652147253349857191230736498725073474761761827043174919382521944349056386305186481198173455293985211104739115063577688592953395294676810655962894343645229199990527683439765973171737546615533185149900878528865499358951458942761341111026253722935261672690109408935429704509667276178562289568318381821903503360000000000000000000000000000000000000000}
The solution proposed by the person "Ugly numbers are numbers that can be divided by 1 OR 2 OR 3 OR 5, the wording of the problem is wrong. This can be solved with dynamic programming by creating an array of length n (where n is the nth ugly number we want to find) and generating multiples of 2, 3 and 5 until we reach n." seems correct. The trick here is keeping the order of the multiples since 2 * 3 == 3 * 2... We need to work on always getting the smallest uggly number that can be generated from the feeds 2, 3 and 5. Here is some sample code:
- daniel.a.p October 02, 2014