49
\$\begingroup\$

Quoting this question on SO (Spoiler alert!):

This question has been asked in an Oracle interview.

How would you divide a number by 3 without using *, /, +, -, %, operators?

The number may be signed or unsigned.

The task is solvable, but see if you can write the shortest code.

Rules:

  • Perform the required integer division (/3)
  • Do not use the non-text-based operators *, /, +, -, or % (or their equivalents, such as __div__ or add()). This also applies to incrementing and decrementing operators, like i++ or i--. Use of operators for string concatenation and formatting are OK. Using these characters for different operators, such as unary - operator for negative numbers, or * to represent a pointer in C is OK as well.
  • Input value can be arbitrarily large (whatever your system can handle), both positive and negative
  • Input can be on STDIN or ARGV or entered any other way
  • Create the shortest code you can to do the above
\$\endgroup\$
  • 1
    \$\begingroup\$ How should the result be rounded when positive? How when negative? \$\endgroup\$ – dfeuer Jun 22 '19 at 22:37

66 Answers 66

2
\$\begingroup\$

Sage Notebook (21)

ZZ(n.digits(3)[1:],3)
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

Mathematica 36 51 42 chars

This is easily achieved in base 3.

IntegerDigits[n,3] converts the absolute value of the number to base 3.

Most takes all but the rightmost digit. This "rightward shift" amounts to integer division by 3.

FromDigits converts back to base 10.

Sign restores, if necessary, the sign.

Sign@n*Most@IntegerDigits[n,3]~FromDigits~3
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

F# (81)

Using inclusive ranges:

let(^)s x=if s<0 then int("-"+string x)else x
let d m =sign m^[3..3..abs m].Length

Alternatively, using strings:

let (^) s x = if s < 0 then int("-" + string x) else x
let d m =
  let n = abs m
  [0..n]
  |> Seq.map (fun i -> i, String.replicate i "aaa")
  |> Seq.takeWhile (fun (i, s) -> s.Length <= n)
  |> Seq.last
  |> fst
  |> (^) (sign m)

This is verbose but it's better than being forced to use loops in many imperative languages. String.replicate is especially valuable.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ This looks like it uses multiplication * to restore the sign bit. \$\endgroup\$ – kernigh May 25 '14 at 16:25
2
\$\begingroup\$

05AB1E, 5 bytes (Non-competing)

3B¨3ö

Try it online!

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

C# with Linq, 51 Bytes

using System.Linq;(n)=>(int)new[]{n,0,0}.Average();

Unfortunately much longer than the Mathematica version of this approach (pesky using statement), but pretty good for C#.

Try it out here.

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

Haskell, 62 52 41 Chars

f n=sum[last$1:[-1|n<0]|i<-[3,6..abs(n)]]

If using sum is not allowed, here's a 52 char solution:

f n|n>0=s|1>0=(-s)where s=length[1|i<-[3,6..abs(n)]]
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

C (gcc), 72 69 59 58 bytes

a,q;f(x){for(a=q=0;a=-~-~-~a,a<=abs(x);)q=-~q;x=x<0?-q:q;}

Try it online!

Edit: Now works with negative arguments.

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

APL (NARS2000), 7 characters

Inspiration

⍎⍞,'r3'

evaluate

text input

,'r3' followed by "r3"

So "15" becomes "15r3" which is NARS2000's rational point notation and evaluates to 5.

Note that the OP states

  • Input can be on STDIN or ARGV or entered any other way
  • Create the shortest code you can to do the above

which allows me to take input as string, and count code length in characters (not bytes – as this is a fairly old challenge that predates the adoption of bytes as default code length unit).

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Scala 96

def d(x:Int)={val y=x.abs;val r=0.to(y).flatMap(List.fill(3)(_)).drop(y).head;if(x==y)r else -r}

I do realize now it is basically the same idea behind some other answers here (Haskell, Clojure and the 2nd take of this one in Ruby, to name a few)... :-/

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

C++ 633 byes (including whitespace; 457 bytes excluding scaffolding)

I know this is not anywhere near the shortest code, but it does have some "advantages". First the code:

#include <climits>
#include <cstdlib>
#include <iostream>
using namespace std;typedef int I;typedef unsigned U;U A(U l,U r){U t;while(r)t=l^r,r=(l&r)<<1,l=t;return l;}
#define N(l)A(~l,1)
#define S(l,r)A(l,N(r))
U M(U l, U r){U p=0;while(r){if(r&1)p=A(p,l);l<<=1;r>>=1;}return p;}U D(U n,U&r){U m=U(1)<<S(M(sizeof(U),CHAR_BIT),1),q=r=0,x=1;while(x){q<<=1;r<<=1;if(n&m)r|=1;if(r>=3)q|=1,r=S(r,3);n<<=1;x<<=1;}return q;}I D(I n,I&r){bool o=n<0;U p=o?N(n):n,s,t;s=D(p,t);r=o?N(t):t;return o?N(s):s;}I main(I c,char**v){I i=1,q,r;while(i<c)q=D(atoi(v[i]),r),cout<<v[i]<<" divided by 3 == "<<q<<" with a remainder of "<<r<<endl,i=A(i,1);}

The advantages over the other solutions, even though it can't win on a purely codegolf basis:

  • It only uses the standard library to obtain the value of CHAR_BIT, atoi, cout, and endl. Consequently, it does not depend on any math routines in the standard library beyond those to convert a string to and from a number. It most definitely does not use any part of the standard library to divide by 3.
  • It at no time uses any of the operators + - * / % (binary or unary, numeric or string). Note that it does use two asterisks to declare a pointer to a pointer to char, but it only uses that to access command line parameters of number to divide.
  • It uses bit manipulation and relational operators exclusively in the division process.
  • If the scaffolding code (main and two of the three include files) is removed, the code that does the actual work of division by 3 is only 457 bytes.
  • I'm pretty sure this code should work on any C++ compiler conforming to the standard and does not exploit any tricks that only work on a subset of compilers or platforms. One possible exception to this is it might not work on a platform that does not use twos complement signed integers, though I don't have access to any platform like that to test that theory. Another possible exception (related) is if automatic signed / unsigned conversions are not supported as they are for most (or all) platforms utilizing twos complement signed integers.

I'm sure there are other ways to make this shorter, but I've spent enough time on it. Mainly I wanted to perform the exercise without any "cheating" via use of any operations from the standard library. By defining functions and macros that perform unary negation, addition, subtraction, multiplication, and division strictly in terms of bit level operations and relational operators, signed (or unsigned) integers can be divided by three. I've hard coded the divisor to 3 to remove a few bytes of code here and there, though adding a parameter to pass in the divisor is fairly trivial.

The signed division function notes the sign of the dividend then calls the unsigned division function with the dividends absolute value. Once the unsigned division returns the unsigned quotient and remainder, the original sign is used to negate the signed quotient and remainder as needed.

Edit: Only after I wrote and submitted my solution did I go look at the original question on SO. Some interesting stuff there, and of course someone had already come up with my solution. FWIW, I did write this on my own! Not that it matters for this old of a question, especially in a codegolf exercise. :)

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

OCTAVE/MATLAB 13

Code where x is an integer. Only works for positive integers and rounds the result up.

length(1:3:x)
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ You could replace length with nnz \$\endgroup\$ – flawr Nov 7 '16 at 22:27
1
\$\begingroup\$

Java 317

I know this is extremely long, and I know this is supposed to be code golf, but for kicks I wanted to write a version that ALSO:

  • Doesn't use the characters [0-9]
  • Doesn't branch

Enjoy :)

import java.util.LinkedList;class Div{int d(int a){int t=getClass().getName().length();char[]s=Integer.toString(a,t).toCharArray();StringBuilder b=new StringBuilder();LinkedList<Character>l=new LinkedList<>();for(char z:s){l.add(z);}l.removeLast();for(char z:l){b.append(z);}return Integer.valueOf(b.toString(),t);}}
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Julia - 29 characters

I'm assuming n as a variable assigned prior to running this line of code.

parseint(chop(base(3,n,2)),3)

Performs the truncation variant (-35 -> -11 not -12). In the current stable release (0.2.1), this approach only works up to base 36 (for division by 36) as parseint only works for alphanumeric text, but in the 0.3 prerelease (based on the forio.com online REPL), it will work up to 62.

Note that the ",2" at the end is necessary to handle numbers less than 3 (or equivalent) in magnitude, as otherwise chop(base(3,n)) will result in either an empty string (for non-negative values) or "-" (for negative values).

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Perl 5, 158 characters

sub t{use integer;$m=unpack(J,U x 8)^(($n=pop)>0&&3);$p=0;for($t= ~0;$t;$t<<=1){$c=$p&($o=$m&1&&$n);$p=($p^$o)>>1;($p,$c)=($p^$c,($p&$c)<<1)while$c;$m>>=1}$p}

This is more than 7 times longer than the answer by memowe, but it runs faster when the input is large, and supports negative inputs. Now you can divide -2147483648 by 3. This defines a sub. t(-2147483648) returns -715827883 because it rounds down.

Division is multiplication!

Division by 3 uses the formula

  • n ÷ 3 = n × (264 ÷ 3) ÷ 264

with an integer constant to approximate 264 ÷ 3. The algorithm multiplies by this constant and drops the lower 64 bits of the 128-bit product. To prevent error, n must be in range for a signed 64-bit integer, and the constant must be

  • ⌊264 ÷ 3⌋ = 5555 5555 5555 555516 if n is negative, or
  • ⌈264 ÷ 3⌉ = 5555 5555 5555 555616 if n is positive.

Multiplication uses an add-and-shift loop. Addition uses bitwise-xor to add and bitwise-and to carry. Shifts preserve the high 64 bits of each 65-bit sum and the final 128-bit product.

Ungolfed code

use strict;
use warnings;

# t($n) is floor($n / 3) with only bitwise operations
sub t {
    use integer; # for signed right shift
    my $n = shift;

    # The formula with 64-bit integers is:
    #   $n / 3 = ($n * (1 << 64) / 3) >> 64
    # If this perl has 32-bit integers, then $m and $t get 32-bit
    # values, so the shifts are by 32.

    # $m = (1 << 64) / 3
    #    = 0x5555 5555 5555 5555 if $n < 0
    #    = 0x5555 5555 5555 5556 else
    my $m = unpack 'J', 'UUUUUUUU';  # Unpack 0x55 bytes.
    $n < 0 or $m ^= 3;               # 0x55 ^ 3 == 0x56

    # Multiplication: $p = ($n * $m) >> 64
    my $p = 0;
    for (my $t = ~0; $t; $t <<= 1) { # Loop 64 times.
    if ($m & 1) {
        # Add and shift: $p = ($p + $n) >> 1
        # Shift early to prevent 65-bit overflow.
        my $c = $p & $n;         # Carry.
        $p = ($p ^ $n) >> 1;     # Add by exclusive-or.
        while ($c) {
        ($p, $c) = ($p ^ $c, ($p & $c) << 1);
        }
    }
    else {
        $p >>= 1;
    }
    $m >>= 1;
    }
    return $p;
}

# test program: divide integers
use POSIX qw(floor);
for my $integer (@ARGV) {
    $integer = int($integer);
    my $have = t($integer);
    my $want = floor($integer / 3);
    printf("%d -> %d (%s)\n", $integer, $have,
       $have == $want ? "correct" : "OFF BY @{[$want - $have]}");
}

The golfed version has some differences:

  • It clobbers global variables.
  • It uses the other value of $m if $n is zero.
  • It replaces the check if ($m & 1) with a new variable $o=$m&1&&$n.
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Jelly, 5 bytes (non-competing)

b3Ṗḅ3

Try it online!

Explanation:

 b3Ṗḅ3 Main link. Arguments: z
⁸      (implicit) z
  3    3
 b     Convert x to base y
   Ṗ   Trim last element off x
     3 3
    ḅ  Convert x from base y
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

APL, 11

3⊥¯1↓3⊥⍣¯1⊢656
218

I'm converting to base 3 and back, removing the last number in the process. Try it on tryapl.org

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Aceto, 6 bytes

ri3:ip
r grabs input
i converts to integer
3 pushes 3 on the stack
: does float division
i converts to integer
p prints it

Try it online!

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Clojure, 74 57 bytes

Improved upon an earlier answer, I'm not sure if I should post this as my own answer or just comment on the original. But this is significantly different way of generating the sequence [0 0 0 1 1 1 2 2 2 ...].

#(let[r(nth(flatten(for[i(range)][i i i]))(Math/abs %))](if(> % 0)r(- r)))

Edit after 1.5 years :D

#((if(> % 0)+ -)(nth(for[i(range)j[i i i]]j)(max(- %)%)))
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Perl 6, 19 bytes

{Rat.new($_,3).Int}

A rational number in Perl 6 is literally defined as a numerator over a denominator. So passing it 7 creates the fraction 7/3 . That fraction is then coerced to an Int. This should work for all ℤ .

Try it online!

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

R, 19 bytes

mean(c(scan(),0,0))

Try it online!

Saw this method above in another language, and easily implemented it in R. And it gives precise answers. Works for positive and negative inputs.

R, 18 bytes

gl(x<-scan(),3)[x]

Slightly shorter solution that only works for positive numbers and performs "actual" integer division.

Try it online!

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

PowerShell, 82 74 bytes

-8 bytes thanks to mazzy

param($n)'-'[$n-ge0]+(-join(0..$n|?{$_}|%{1})-replace111,0-replace1|% Le*)

Try it online!

Bug-fix of Joseph Alcorn's answer to handle negatives correctly.

83 bytes to have 0 instead of -0

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ -0 is not very nice. Powershell knows how to make ranges with with negative bounds :) \$\endgroup\$ – mazzy Jun 24 '19 at 17:52
  • \$\begingroup\$ @mazzy If you go 1..$n with a negative, you get two extra iterations. 0..$n is an extra tick as well because you can't do 0..--$n(but can probably be fixed with minimal fuss) \$\endgroup\$ – Veskah Jun 24 '19 at 17:56
  • 1
    \$\begingroup\$ 74 bytes :) \$\endgroup\$ – mazzy Jun 25 '19 at 6:28
  • \$\begingroup\$ is This also applies to incrementing and decrementing operators means Do not use incrementing and decrementing operators? Ok. Then your approach is best. \$\endgroup\$ – mazzy Jun 25 '19 at 13:56
  • 1
    \$\begingroup\$ @mazzy Yep, those are not to be used. \$\endgroup\$ – Veskah Jun 25 '19 at 14:04
1
\$\begingroup\$

Python 3, 31 38 29 chars

print(eval(input()+"%c3"%47))

Edited to add a print statement.

Edited to avoid use of int call.

Kind of cheating. Eval will evaluate and return any operations passed as a string as if it were code. chr() converts an int to the character with that ASCII value, and 47=/. Pass in the / with standard string formatting.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ This looks great! It's not cheating. \$\endgroup\$ – NoOneIsHere Feb 8 '17 at 19:06
  • 2
    \$\begingroup\$ This is invalid as it is for the lack of print statement, sorry. Simple fix though, just add a print statement. Also, you can make it python2 and skip the 'int()' part. \$\endgroup\$ – Rɪᴋᴇʀ Feb 8 '17 at 19:07
  • 2
    \$\begingroup\$ I only say 'cheating' because it does actually use the division operator, it's just a bit hidden. \$\endgroup\$ – mypetlion Feb 8 '17 at 19:49
0
\$\begingroup\$

32 characters in Burlesque:

0\/r@{1\/.-<-2\/.-<-}{L[1.>}w!-]

assuming the number to divide is already on the stack. (see here in action).

How does it work? It generates a list of numbers 0..n and then removes one from the left and two from the right until only one number is left. Of course this method only works with numbers that are divisible by 3.

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Perl using an eval to compute a string version of x/3.

Perl 5.8 Version

print eval join' ','int',$ARGV[0],map{chr}47,51

Perl 5.10 Version

say print eval join' ','int',$ARGV[0],map{chr}47,51
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I'm not sure if the exactly meets the criteria of "without using the / operator". It still uses it, it's just hidden in the code as character 47. \$\endgroup\$ – primo Dec 15 '12 at 15:54
  • \$\begingroup\$ You are correct, this just hides it. Either way, my solution isn't nearly as good as memowe's version using regular expressions. \$\endgroup\$ – xxfelixxx Dec 17 '12 at 3:11
0
\$\begingroup\$

perl 23

$_=()=(1x$_)=~/(111)/g

usage:

> echo 1e4|perl -pe'$_=()=(1x$_)=~/(111)/g'
3333

Doesn't work with negatives.

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Mathematica (assorted)

Dividing 9 by 3 (but should work for arbitray input). The second version outputs just the number, while the first will offer additional braces (not sure about what is deemed correct, pick your count):

9Inverse[{{3}}]              (*15*)
9Inverse[{{3}}][[1,1]]       (*22*)

LinearSolve[{{3}},{9}]       (*22*)
LinearSolve[{{3}},{9}][[1]]  (*27*)
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Hexagony, 28 (Non-competing, only unsigned)

?$\<@'\.|!"1.(|{'&.{&.1\()\$

Try It Online!

Haven't got any Bitwise operators, so either can't join (like BF) or break the rules with increments and decrements. I chose the latter as I ...

...just want to share the facts that a hexagon is a polygon with 6 sides, and the number 6 has a factor 3. This is an "advantage" to Hexagons so I hope this will be interesting.

Expanded version

   ? $ \ <
  @ ' \ . |
 ! " 1 . ( |
{ ' & . { & .
 1 \ ( ) \ $
  . . . . .
   . . . .

? gets the input, and $ skips a mirror then we hit < the branch.

If the number is <=0 it goes to the corner then to {!@ which prints the "counter" (explained below) and ends the program.

(Else) If it is >0,

  1. decrement it and increase the counter by 1 (located relatively at { as left neighbour and goes back with ").
  2. Step back to the right and copy.
  3. Step back to the right and copy again.
  4. Goes back to the branch after a few reflections.

Anyone who wants to understand how this ends with graphics? I hope there is someone who wants to know more about Hexagony and know why keep stepping back to the right will in turn accumulates the counter. :P

I can't use the operators +-*/%. Can I use :? (The integer division) Obviously not - I'll be breaking the rules. Sadly I am already breaking the rules with increments and decrements. So I imposed myself to an unintended rule - not using / as an operator for reflection :) Whole program is +-*/%-free. May need a side length 5 hexagon to make one that can take care of the negatives...

Oh I just love hexagons.

Hexagon Edition, also 28, another way to get back into the loop.

?$|<@'\H|!"EX(|{'AG{&|O&N)\$
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Python 2, 16 bytes (Joke Answer)

print input()//3

// is not the same as /, the division operator. //, a token in and of itself, is the floor-division operator. Example: 4.5 // 2 == 2. Note that this answer exploits a loophole in the question, and can be considered a joke. However, it is within the technical rules because the question says you cannot use the / operator. Although this answer uses the character "/", it never uses it as an operator.

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Python 3, 61 bytes

from numpy import*;f=lambda x:int(base_repr(x,base=3)[:-1],3)

This doesn't win, but I think it's a clever method that hasn't been used in the other Python entries, so I'm posting it here.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ if using numpy import numpy;print(int(numpy.mean([x,0,0]))) for 44? \$\endgroup\$ – Zulfiqaar Jun 20 '19 at 16:53
0
\$\begingroup\$

Octave/MATLAB, 7 bytes

@(x)3\x

Try it online!

I'm not entirely sure whether or not this would count as cheating. It's not using one of the specifically listed operators (+-%/*). MATLAB has a right divide operator which divides a number on the right by a number on the left.

I'll delete this answer if the consensus that it is cheating.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.