10 ms·
Divide a number by 3 without using * / + - % operators
- Tloewald 14y agoIf n < 0 record sign and invert. (If we can't use unary "-" then just use two blocks of code). Set dividend to 0. Loop against n, incrementing loop index by 3. Increment dividend by 1 per loop iteration. Invert dividend if we inverted n. Dividend is your answer (or add the remainder to a more precise floating point result). No bit twiddling. Small RAM footprint. Obviously correct. (This is really just an unoptimized version of the "clever" solution.) For Oracle though -- create a database of numbers and their thirds and then lookup the answer.
- ColinWright 14y agoHow do you increment without using "+"?
- sunir 14y agoIncrement operator ++
- ciupicri 14y agoThen as one of the comments says why not use the /= operator directly?
- femto 14y agoInvert all the least significant bits, up to and including the least significant zero.
- Tloewald 14y agoNice suggestion if we disallow ++ and still simpler than most of the other proposed solutions.
- podperson 14y ago++ Or += which is needed for the bitshift solution.
- dedward 14y agoIF you have a ruler, we can do it with some origami folds and measure the result. Or a slide rule, though that's possibly cheating (technically you'd be dividing....)
- _delirium 14y agoTangentially related: although you're probably suggesting trisecting an edge with origami folds (which is straightforward), the mention of dividing by three using physical methods reminded me of the classic trisecting-an-angle problem, which apparently is also solvable with origami folds [1], even though it isn't solvable with compass and straightedge [2]. [1] https://www.math.lsu.edu/~verrill/origami/trisect/ https://www.math.lsu.edu/~verrill/origami/trisect/ [2] http://en.wikipedia.org/wiki/Angle_trisection http://en.wikipedia.org/wiki/Angle_trisection
- dedward 14y agoYup - they're the same thing... you trisect the angle from the corner, and end up with an edge neatly in thirds. Surprised me when I found it too - neat stuff, paper.
- mjwalshe 14y agoBut a huge number of bonus geek points for pulling out a slide rule in an interview :-)
- ars 14y agoConsidering all computers can be build out of NAND gates, just simulate such a computer using only the NOT and AND operators. You would have to handle each of the bits individually.
- Foy 14y agoAny explanation for this solution: (I'm not overly familiar with C, and I'm very curious as to how it works) #include <stdio.h> #include <stdlib.h> #include <string.h> int main() { FILE * fp=fopen("temp.dat","w+b"); int number=12346; int divisor=3; char * buf = malloc(number); memset(buf,0,number); fwrite(buf,number,1,fp); rewind(fp); int result=fread(buf,divisor,number,fp); printf("%d / %d = %d", number, divisor, result); free(buf); fclose(fp); return 0; }
- verroq 14y agoWrite 12346 zeros into the file. Read the file back in blocks of size 3. fread returns number of blocks read.
- to3m 14y agofread and fwrite do their thing on N chunks of M bytes each, and fread returns the number of chunks that it managed to read. So the write writes 1 chunk of `number' byte each, then the read reads `number' chunks of `divisor' bytes each (obviously this value will be larger than the number of bytes in the file). And by returning the number of `divisor'-byte chunks needed to read a file of `number' bytes in size, you get your answer. This just goes to prove that fread and fwrite are the biggest pile of crap.
- pif 14y agoHe writes "number" bytes into a temporary file and then, starting from the beginning, re-reads them in blocks of "divisor" bytes each. "fread" returns the number of full blocks read from the stream.
- codeka 14y ago> This question has been asked in an Oracle interview. I don't usually sit on the side of fence that complains about "write a function that does X" style questions in interviews, but I can't see how this is useful at all. This just seems like one of those things that you either know off the top of your head, or you don't. If you asked me to derive the addition operation using only bit level operators, I might be able to come up with it, but it'd probably take me much longer than an interview allows. But to come up with divide is just not going to happen. So if you don't know the answer off the top of your head, what use is this question?
- Foy 14y agoHello candidate. Please state in reverse alphabetical order every algorithm you have memorized. For completeness, provide an implementation of each algorithm on this sheet of paper.
- Someone 14y agoAs with all such questions, it attempts to test (creative) thinking. Also as with (almost) all such questions, knowledge can prevent that. For this example, 1/3, in binary, is 0.0101010101… From there, writing out the long multiplication will give hints towards a solution. Untested, so likely erroneous: uint n = 12356; uint result = 0; while( n > 0) { n >>= 2; result += n; // cheating } If you do not want to cheat, write a function that computes x minus 1 using but twiddling, and add a loop.
- aristidb 14y agoThe result is off by 1. :) Not bad though!
- Retric 14y agoYea, but you can correct for that. Because it's always going to be close but low. So just1 add number to it's self twice and if that's low add 1, repeat as needed. PS: Or because there is no need for it to be fast just start with zero keep adding 1 until 3x+3 > n.
- chipsy 14y agoLookup table. Edit: I should add, the problem never said I didn't have infinite memory or computational resources.
- jiggy2011 14y agoOk, but how do you create the lookup table?
- lincolnq 14y agoI don't know, but how do you compile any of these C programs?
- johnpmayer 14y agofor i... { append i append i + 0.333 append i + 0.666 }
- jiggy2011 14y agoYou can't use the + operator.
- alex_c 14y agoMechanical Turk. A budget limit wasn't mentioned either :)
- jakejake 14y agoThis should be exactly the kind of out-of-the-box thinking that these questions find. But something tells me the person who asked this question would not have been impressed, which is sad. They probably just want someone who memorized a division implementation in assembly.
- smackmybishop 14y agoAssuming unspecified resources are infinite without confirming? This is not good problem solving. You should not be impressed.
- latimer 14y agoSimilar question except without using bitwise operators: http://stackoverflow.com/questions/2306830/addition-without-using-arithmetic-or-bitwise-operators http://stackoverflow.com/questions/2306830/addition-without-...
- no_gravity 14y agoIn Javascript: http://tinyurl.com/cwcqles http://tinyurl.com/cwcqles
- femto 14y agoA glimmer of a solution: 1/3 = 0.010101... base 2. x = let x0,x1,...,xN-2,xN-1 (MSB is x0 and LSB is xN-1) Now y = x/3 = x * 1/3, where y=(y0,y1,...), so a long multiplication will look something like (being sloppy about exact bit positions): x0,x1,...,xN-2,xN-1 * 0.010101... ------------------------- x0,x1,x2,x3,x4,x5...,xN-2,xN-1 x0,x1,x2,x3,x4,x5...,xN-2,xN-1 x0,x1,x2,x3,x4,x5...,xN-2,xN-1 Let's shorten it by grouping the bits in pairs, so BN=(b2N,b2N+1). X0,X1,X2,X3 X0,X1,X2,X3 X0,X1,X2,X3 Y0,Y1,Y2,Y3,Y4,Y5 or: Y0 =X0 or X0 +1 Y1=X1+X0+carry =X1+Y0 or X1+Y0+1 (extra bits of carry are in Y0) Y2=X2+X1+X0+carry=X2+Y1 or X1+Y1+1 (extra bits of carry are in Y1) The key is that in the above, there is only ever a single bit being carried between bit pairs, as the "01" pattern in 1/3 base 2 limits how carries propagate. Here's a partial solution, which only works fro a few trivial cases (eg 2^N) since I haven't accounted for the possability of a single bit carry. For a full solution, maybe a conditional is required and an additonal logic operation or two to perform an increment on a pair of bits? div3(int x) { int y=0; while(x) y ^= (x>>=2) return(y) } Can anyone complete it? Edit: formatting. Beats me how to do fixed width properly. Edit: Oops. In the time it took me to write this qntm got there first!
- twentysix 14y agoI found this after a little bit of searching and it seems to work. n/3 = pow(2, log2(n) - log2(3))
- wccrawford 14y agoYou used -
- jz10 14y agoCan this be an answer? (Python) x = 9 x.__div__(3)
- chimmy 14y agodivide every possible number with 3 and store key value pairs. Return, the answer in O(1), when asked to divide.
- mccoyst 14y agoIs anyone else disappointed that the best answer (the standard div() function) was passed over in favor of massively inefficient bit-twiddling wankery?
- stephencanon 14y agoYes! I was going to say exactly this. Know your standard library, citizen!
- peteretep 14y agoSimple Perl solution, using string/numeric coercion. Don't think there's anything here you couldn't do in C. Uses a 30-item lookup table. I've made it round, rather than adding precision logic for recurring 3s... https://gist.github.com/3206885 https://gist.github.com/3206885
- frankgrimes97 14y agoHow about the following? new java.math.BigInteger("10").divide(new java.math.BigInteger("3")); or new java.math.BigDecimal("10").divide(new java.math.BigDecimal("3"), java.math.RoundingMode.HALF_UP);
- jurre 14y agothe stackoverflow question is labeled 'c'
- gergely 14y agoMaybe I'm missing something but what about operator overloading?
- gergely 14y agoASCII codes.
- knowaveragejoe 14y ago> This was oracle so what parts of oracle were you allowed to use? – Hogan Nearly spat out my coffee.
- mmphosis 14y agoI liked this historical reference to the Setun computer. http://stackoverflow.com/questions/11694546/divide-a-number-by-3-without-using-operators http://stackoverflow.com/questions/11694546/divide-a-number-... http://en.wikipedia.org/wiki/Setun http://en.wikipedia.org/wiki/Setun
- Kilimanjaro 14y agoBrute force in python: n = 12345 # your input s = ''.zfill(n) # fill as many zeroes while len(s)>3: s=s[3:] # trim 3 zeroes each time print 'divisible by 3' if len(s)==3 else 'nop'
- Kilimanjaro 14y agoBtw, a loop counter will tell you the result and the reminder will be len(s) at the end.
- beambot 14y agoUse slicing to do the counting for you: n_divideby_3 = lambda n: len(''.zfill(n)[2::3])
- S_A_P 14y agoIf I had a dollar for every time in the 12 or so years I have written code as a profession, I have needed to implement tricks such as this I would have... 1 dollar. I get that a company wants to hire smart people who can problem solve and think outside the box, but it doesn't really represent reality. I think if you had someone who wrote code like that you would have a maintenance nightmare since most people don't write code like that. Of course not all situations are like mine. I write a few layers of abstraction away from the hardware, and live mostly in the managed code world. A low level/embedded systems developer may need to know these things.
- Daniel_Newby 14y agoIt is a question about binary arithmetic. If you understand how computers work, you can get the solution. If you understand the divide and conquer approach, you can make a fast and efficient solution. Why would it be a maintenance nightmare?! It is arithmetic with one input and one output! If an organization cannot validate that, they have no chance of making good software.
- S_A_P 14y agoI disagree. This sort of thing is an exception, and not a rule. I would much rather a developer knows their framework, knows design patterns, separation of concerns, and most importantly writing clean code. As I said before, for enterprise applications, this sort of thing is rarely if ever necessary to know. Having someone who likes to bit twiddle just because they find it interesting is not always good for writing a solid maintainable code base.
- Daniel_Newby 14y agoAn team can certainly make a lot of progress using the skills you list. But that is not sufficient to solve tough problems. You really do need at least a few people who understand things like memory hierarchies, Bloom filters, statistics, etc. To find these people you have to interview for them.
- psykotic 14y agoThe top-voted answer implements addition. If you're allowed to do that, the subtraction-based division algorithm is easy and foolproof if not as fast: u32 add(u32 x, u32 y) { u32 z = 0; for (u32 c = 0, m = 1; m; m <<= 1) z |= (x ^ y ^ c) & m, c = ((x & y) | (x & c) | (y & c)) << 1; return z; } u32 neg(u32 x) { return add(~x, 1); } u32 sub(u32 x, u32 y) { return add(x, neg(y)); } u32 lt(u32 x, u32 y) { return sub(x, y) >> 31; } u32 div3(u32 x) { u32 q = 0; assert(lt(-1, x)); // x >= 0 iff -1 < x while (!lt(x, 3)) x = sub(x, 3), q = add(q, 1); return q; }
- deleted 14y ago[deleted]
- VLM 14y agoI read the stack overflow. So someone at Oracle is dumb enough to want to reimplement / and/or wants to see if a future hire is dumb enough to be intimidated by a manager into doing something dumb (dumb like, say, reimplement /) OK my solution is connect to a postgres sql DB server and something very much like "SELECT WIDTH_BUCKET(389, 999, 0, 333);" and the result will be something like 129. width_bucket asks for a sample, the highest bucket, the lowest bucket, how many buckets, and tells you which bucket to dump the sample into. You know, for histograms and stuff like that. So you make the largest bucket max_int or 999 in this easy scenario, and the number of buckets precisely 1/3 the number of buckets or 333 in this easy case, and postgres database will figure out the number of the bucket to stick your sample into, which coincidentally happens to numerically match 1/3 the sample. Its possible Oracle has a function similar to width_bucket from postgres, but I have no idea because a Oracle license costs about 10 times the value of my house so I can't afford it, probably because they pay people to reimplement /. Another fun way to attack this problem would be to go all trig on them and try to convince them its impossible to divide by 3 because you can't trisect an angle using classical greek construction techniques. Then you hit them with galois theory as relates to solving cubic equations, until their brains bleed and/or you get the job and/or removed by security. This stuff is all 200 years old, or so, but you'll still find cranks who think they can trisect angles using classical greek construction techniques. Maybe being smart enough to understand that overqualifies the applicant from working at a place that things reimplementing / is a wise use of brain power.
- toomuchcoffee 14y agoHmm, what would be a typical experienced, successful programmer's response to this kind of a question if it were asked in, you know, a real-life setting? "Look at bit-shift operators, and how they work on unsigned integers. Then think & and ^ and how they relate to addition (adders, after all, have to be implemented in terms of elementary operations like those). It's all pretty straightforward from there. Go the whiteboard and walk you through it? Huh? Look, it's an interesting problem, but I've got some regression tests to get straightened out by the end of the day that are like, totally messed up. They were written by some guy we hired on the basis of his ability to solve puzzle problems, but just ended up totally slacking and never tying the ends off of anything he did." Really now, why should one's response in an interview be any different?
- crusso 14y agoAs a hiring manager for the last 15+ years, I would LOVE that kind of response. That kind of response would save me a tremendous amount of time and enormous headaches dealing with a bad hire. I would thank you for your honesty, ask you a couple of perfunctory questions so it didn't seem too awkward and then let you go on your way in life to be someone else's problem. Working on real projects that people actually want to pay for means working somewhat on the edge. Things go wrong. There are crunch time when solutions have to be delivered. The last thing I want at those times is to have to depend upon some mommie's special little snowflake who was too self-important to gamely work through some puzzle exercises during an interview for a job he claimed he wanted. That little snowflake will melt every time and leave me and the rest of his team to fend for itself. No thanks.
- toomuchcoffee 14y agomommie's special little snowflake Aww.
- thirsteh 14y agoPen and paper? Nobody ever said it had to be done using a computer :)