Divide a number by 3 without using *, /, +, -, % operators

Question

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

Answer 1

J, 45 44 10 chars

".,&'r3'":

Works with negatives:

".,&'r3'": 15
5
   ".,&'r3'": _9
_3
   ".,&'r3'": 3e99
1e99

": - format as text

,&'r3' - append r3 to the end

". - execute the string, e.g. 15r3

Answer 2

C, 167503724710

Here's my solution to the problem. I admit it is unlikely to win a strict code golf competition, but it doesn't use any tricks to indirectly call built-in division functionality, it is written in portable C (as the original Stack Overflow question asked for), it works perfectly for negative numbers, and the code is exceptionally clear and explicit.

My program is the output of the following script:

#!/usr/bin/env python3
import sys

# 71
sys.stdout.write('''#include <stdint.h>
#include <stdio.h>
int32_t div_by_3(int32_t input){''')

# 39 * 2**32
for i in range(-2**31, 2**31):
    # 18 + 11 + 10 = 39
    sys.stdout.write('if(input==%11d)return%10d;' % (i, i / 3))

# 95
sys.stdout.write(r'''return 7;}int main(int c,char**v){int32_t n=atoi(a[1]);printf("%d / 3 = %d\n",n, div_by_3(n));}''')

Character count: 71 + 39 * 2**32 + 95 = 167503724710

Benchmarks

It was asked how long this would take and how much memory it would use, so here are some benchmarks:

• Script execution time — Running ./test.py | pv --buffer-size=1M --average-rate > /dev/null for about 30 seconds gives a rate of about 14.8 MB/s. The rate of output can reasonably be assumed to be roughly constant, so the running time to completion should be about 167503724710 B / (14.8 * 1048576 B/s) ≈ 10794 s.
• Compilation time — The TCC compiler claims to compile C code at 29.6 MB/s, which makes for a compilation time of 167503724710 B / (29.6 * 1048576 B/s) ≈ 5397 s. (Of course this can run in a pipeline with the script.)
• Size of compiled code — I tried estimating it using ./test.py | tcc -c - -o /dev/stdout | pv --buffer-size=1M --average-rate > /dev/null, but it seems tcc doesn't output anything until it reads the entire source file in.
• Memory usage to run — Since the algorithm is linear (and tcc doesn't optimize across lines), the memory overhead should be only a few kilobytes (apart from the code itself, of course).

Answer 3

Ruby 28

b=->n{n.to_s(3).chop.to_i 3}

To divide by 3 we just need to remove the trailing zero in base 3 number: 120 -> 11110 -> 1111 -> 40

Works with negatives:

ice distantstar:~/virt/golf [349:1]% ruby ./div3.rb
666
222
ice distantstar:~/virt/golf [349]% ruby ./div3.rb
-15        
-5

Ruby, 6045

Alternatively, w/o using base conversion:

d=->n{x=n.abs;r=(0..1.0/0).step(3).take(x).index x;n>0?r:-r}

d=->n{(r=1.step(n.abs,3).to_a.size);n>0?r:-r}

Answer 4

Mathematica, 13 chars

Mean@{#,0,0}&

Answer 5

JavaScript, 56

alert(Array(-~prompt()).join().replace(/,,,/g,1).length)

Makes a string of length n of repeating ,s and replaces ,,, with 1. Then, it measures the string's resulting length. (Hopefully unary - is allowed!)

Answer 6

Python, 41 38

print"-"[x:]+`len(xrange(2,abs(x),3))`

xrange seems to be able to handle large numbers (I think the limit is the same as for a long in C) almost instantly.

>>> x = -72
-24

>>> x = 9223372036854775806
3074457345618258602

Answer 7

Haskell, 90 106

d n=snd.head.dropWhile((/=n).fst)$zip([0..]>>=ν)([0..]>>=replicate 3>>=ν);ν q=[negate q,q]

Creates an infinite (lazy) lookup list [(0,0),(0,0),(-1,0),(1,0),(-2,0),(2,0),(-3,-1),(3,1), ...], trims all elements that don't match n (/= is inequality in Haskell) and returns the first which does.

This gets much simpler if there are no negative numbers:

25 27

(([0..]>>=replicate 3)!!)

simply returns the nth element of the list [0,0,0,1,1,1,2, ...].

Answer 8

C#, 232 bytes

My first code golf... And since there wasn't any C# and I wanted to try a different method not tried here, thought I would give it a shot. Like some others here, only non-negative numbers.

class l:System.Collections.Generic.List<int>{}class p{static void Main(string[] g){int n=int.Parse(g[0]);l b,a=new l();b=new l();while(a.Count<n)a.Add(1);while(a.Count>2){a.RemoveRange(0,3);b.Add(1);}System.Console.Write(b.Count);}}

Ungolfed

class l : System.Collections.Generic.List<int>
{ }
class p
{
    static void Main(string[] g)
    {
        int n = int.Parse(g[0]);
        l b, a = new l();
        b = new l();
        while (a.Count < n) a.Add(1);
        while (a.Count > 2)
        {
            a.RemoveRange(0, 3);
            b.Add(1);
        }
        System.Console.Write(b.Count);
    }
}

Answer 9

Perl (26 22)

$_=3x pop;say s|333||g

This version (ab)uses Perl's regex engine. It reads a number as the last command line argument (pop) and builds a string of 3s of this length ("3" x $number). The regex substitution operator (s///, here written with different delimitiers because of the puzzle's rules and with a global flag) substitues three characters by the empty string and returns the number of substitutions, which is the input number integer-divided by three. It could even be written without 3, but the above version looks funnier.

$ perl -E '$_=3x pop;say s|333||g' 42
14

Answer 10

JavaScript, 55

alert(parseInt((~~prompt()).toString(3).slice(0,-1),3))

If one can't use -1, then here is a version replacing it with ~0 (thanks Peter Taylor!).

alert(parseInt((~~prompt()).toString(3).slice(0,~0),3))

Answer 11

Python 42

int(' -'[x<0]+str(len(range(2,abs(x),3))))

Since every solution posted here that Ive checked truncates decimals here is my solution that does that.

Python 50 51

int(' -'[x<0]+str(len(range([2,0][x<0],abs(x),3))))

Since python does floor division, here is my solution that implements that.

Input integer is in the variable x.

Tested in Python 2.7 but I suspect it works in 3 as well.

Answer 12

C, 160 chars

Character by character long division solution using lookup tables, i.e. without string atoi() or printf() to convert between base 10 strings and integers.

Output will sometimes include a leading zero - part of it's charm.

main(int n,char**a){
char*s=a[1],*x=0;
if(*s==45)s=&s[1];
for(;*s;s=&s[1])n=&x[*s&15],x="036"[(int)x],*s=&x["000111222333"[n]&3],x="012012012012"[n]&3;
puts(a[1]);
}

Note:

• abuses array access to implement addition.
• compiles with clang 4.0, other compilers may barf.

Testing:

./a.out -6            -2
./a.out -5            -1
./a.out -4            -1
./a.out -3            -1
./a.out -2            -0
./a.out -1            -0
./a.out 0             0
./a.out 1             0
./a.out 2             0
./a.out 3             1
./a.out 4             1
./a.out 5             1
./a.out 6             2
./a.out 42            14
./a.out 2011          0670

Answer 13

C 83 characters

The number to divide is passed in through stdin, and it returns it as the exit code from main() (%ERRORLEVEL% in CMD). This code abuses some versions of MinGW in that when optimizations aren't on, it treats the last assignment value as a return statement. It can probably be reduced a bit. Supports all numbers that can fit in to an int

If unary negate (-) is not permitted: (129)

I(unsigned a){a=a&1?I(a>>1)<<1:a|1;}main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:I(~a);for(c=0;a<~1;a=I(I(I(a))))c=I(c);b=b<0?I(~c):c;}

If unary negate IS permitted: (123)

I(unsigned a){a=a&1?I(a>>1)<<1:a|1;}main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:-a;for(c=0;a<~1;a=I(I(I(a))))c=I(c);b=b<0?-c:c;}

EDIT: ugoren pointed out to me that -~ is an increment...

83 Characters if unary negate is permitted :D

main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:-a;for(c=0;a<~1;a=-~-~-~a)c=-~c;b=b<0?-c:c;}

Answer 14

Java 86 79

Assume the integer is in y:

Converts to a string in base 3, removes the last character ( right shift ">>" in base 3 ), then converts back to integer.

Works for negative numbers.

If the number, y, is < 3 or > -3, then it gives 0.

System.out.print(~2<y&y<3?0:Long.valueOf(Long.toString(y,3).split(".$")[0],3));

First time posting on code golf. =) So can't comment yet.

Thx Kevin Cruijssen for the tips.

Answer 15

C, 139 chars

t;A(a,b){return a?A((a&b)<<1,a^b):b;}main(int n,char**a){n=atoi(a[1]);for(n=A(n,n<0?2:1);n&~3;t=A(n>>2,t),n=A(n>>2,n&3));printf("%d\n",t);}

Run with number as command line argument

• Handles both negative and positive numbers

Testing:

 ./a.out -6            -2
 ./a.out -5            -1
 ./a.out -4            -1
 ./a.out -3            -1
 ./a.out -2            0
 ./a.out -1            0
 ./a.out 0             0
 ./a.out 1             0
 ./a.out 2             0
 ./a.out 3             1
 ./a.out 4             1
 ./a.out 5             1
 ./a.out 6             2
 ./a.out 42            14
 ./a.out 2011          670

Edits:

• saved 10 chars by shuffling addition (A) to remove local variables.

Answer 16

C, 81 73 chars

Supports non-negative numbers only.

char*x,*i;
main(){
    for(scanf("%d",&x);x>2;x=&x[~2])i=&i[1];
    printf("%d",i);
}

The idea is to use pointer arithemtic. The number is read into the pointer x, which doesn't point anywhere. &x[~2] = &x[-3] = x-3 is used to subtract 3. This is repeated as long as the number is above 2. i counts the number of times this is done (&i[1] = i+1).

Answer 17

ZSH — 31 20/21

echo {2..x..3}|wc -w

For negative numbers:

echo {-2..x..3}|wc -w

With negative numbers (ZSH + bc) — 62 61

I probably shouldn't give two programs as my answer, so here's one that works for any sign of number:

echo 'obase=10;ibase=3;'`echo 'obase=3;x'|bc|sed 's/.$//'`|bc

This uses the same base conversion trick as Artem Ice's answer.

Answer 18

Python2.6 (29)(71)(57)(52)(43)

z=len(range(2,abs(x),3))
print (z,-z)[x<0]

print len(range(2,input(),3))

Edit - Just realized that we have to handle negative integers too. Will fix that later

Edit2 - Fixed

Edit3 - Saved 5 chars by following Joel Cornett's advice

Edit4 - Since input doesn't have to be necessarily be from STDIN or ARGV, saved 9 chars by not taking any input from stdin

Answer 19

Javascript, 47 29

Uses eval to dynamically generate a /. Uses + only for string concatenation, not addition.

alert(eval(prompt()+"\57"+3))

EDIT: Used "\57" instead of String.fromCharCode(47)

Answer 20

Ruby (43 22 17)

Not only golf, but elegance also :)

p Rational gets,3

Output will be like (41/1). If it must be integer then we must add .to_i to result, and if we change to_i to to_f then we will can get output for floats also.

Answer 21

TI-Basic, 8 bytes

Winner? :)

int(mean({Ans,0,0

P.S. Rounds towards infinity for negative numbers (see here for why). To round to zero instead, replace int( with iPart( for no byte change.

Test cases

-4:prgmDIVIDE
              -2
11:prgmDIVIDE
               3
109:prgmDIVIDE
              36

Answer 22

SmileBASIC, 58 51 36 bytes (no mathematical functions!)

INPUT N
BGANIM.,4,-3,N
WAIT?BGROT(0)

Explanation:

INPUT N           'get input
BGANIM 0,"R",-3,N 'smoothly rotate background layer 0 by N degrees over 3 frames
WAIT              'wait 1 frame
PRINT BGROT(0)    'display angle of layer 0

The program moves the background layer smoothly over 3 frames, and then gets the angle after 1 frame, when it has traveled 1/3 of its total distance.

Float division version, 38 bytes:

INPUT N
BGANIM.,7,-3,N
WAIT?BGVAR(0,7)

Explanation:

INPUT N           'input
BGANIM 0,"V",-3,N 'smoothly change layer 0's internal variable to N over 3 frames
WAIT              'wait 1 frame
PRINT BGVAR(0,7)  'display layer 0's internal variable

Answer 23

R

These only work with positive integers:

max(sapply(split(1:x,1:3), length))
# Gives a warning that should be ignored

Or:

min(table(rep(1:3, x)[1:x]))

Or:

length((1:x)[seq(3,x,3)])

Or:

sum(rep(1,x)[seq(3,x,3)])

[[EDIT]] And an ugly one:

trunc(sum(rep(0.3333333333, x)))

[[EDIT2]] Plus probably the best one - inspired by the matlab code above by Elliot G:

length(seq(1,x,3))

Answer 24

Haskell 41 39 chars

Works with the full set of positive and negative integers

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

First creates a list 1's or (-1)'s (depending on the sign of the input) for every third integer from 0 up until the input n. abs(n) for negative numbers inclusive.

e.g n=8 -> [0,3,6]

It then returns the sum of this list.

Answer 25

Python 3, 72 bytes

f=lambda x:x and s(x>>1,f(x>>1))
s=lambda x,y:y and s(x^y,(~x&y)<<1)or x

Try it online!

A bitwise solution consisting of two recursive functions, one to calculate third, the other to subtract. Because multiplying and dividing by 2 is easy to do bitwise, we can use the fact:
\$X/3=X/2-(X/2)/3\$
to recursively find the third.

It does produce some weird rounding patterns for non-multiples of three.

0 -> 0 (0)
1 -> 0 (0.333...)
2 -> 1 (0.666...)
3 -> 1 (1)
4 -> 1 (1.333...)
5 -> 1 (1.666...)
6 -> 2 (2)
7 -> 2 (2.333...)
8 -> 3 (2.666...)
9 -> 3 (3)
10 -> 4 (3.333...)
11 -> 4 (3.666...)
12 -> 4 (4)
13 -> 4 (4.333...)
14 -> 5 (4.666...)
15 -> 5 (5)

Answer 26

Python 2.x, 54 53 51

print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))

Where _ is the dividend and is entered as such.

>>> x=-19
>>> print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))
- 6

Note: Not sure if using the interactive interpreter is allowed, but according to the OP: "Input can be on STDIN or ARGV or entered any other way"

Edit: Now for python 3 (works in 2.x, but prints a tuple). Works with negatives.

Answer 27

C++, 191

With main and includes, its 246, without main and includes, it's only 178. Newlines count as 1 character. Treats all numbers as unsigned. I don't get warnings for having main return an unsigned int so its fair game.

My first ever codegolf submission.

#include<iostream>
#define R return
typedef unsigned int U;U a(U x,U y){R y?a(x^y,(x|y^x^y)<<1):x;}U d(U i){if(i==3)R 1;U t=i&3,r=i>>=2;t=a(t,i&3);while(i>>=2)t=a(t,i&3),r=a(r,i);R r&&t?a(r,d(t)):0;}U main(){U i;std::cin>>i,std::cout<<d(i);R 0;}

uses shifts to divide number by 4 repeatedly, and calculates sum (which converges to 1/3)

Pseudocode:

// typedefs and #defines for brevity

function a(x, y):
    magically add x and y using recursion and bitwise things
    return x+y.

function d(x):
    if x = 3:
        return 1.
    variable total, remainder
    until x is zero:
        remainder = x mod 4
        x = x / 4
        total = total + x
    if total and remainder both zero:
        return 0.
    else:
        return a(total, d(remainder)).

As an aside, I could eliminate the main method by naming d main and making it take a char ** and using the programs return value as the output. It will return the number of command line arguments divided by three, rounded down. This brings its length to the advertised 191:

#define R return
typedef unsigned int U;U a(U x,U y){R y?a(x^y,(x|y^x^y)<<1):x;}U main(U i,char**q){if(i==3)R 1;U t=i&3,r=i>>=2;t=a(t,i&3);while(i>>=2)t=a(t,i&3),r=a(r,i);R r&&t?a(r,d(t)):0;}

Answer 28

Golfscript - 13 chars

~3base);3base

Answer 29

PowerShell 57 or 46

In 57 characters using % as the PowerShell foreach operator, not modulo. This solution can accept positive or negative integers.

(-join(1..(Read-Host)|%{1})-replace111,0-replace1).Length

In 46 characters if * is allowed as the string repetition operator, not multiply. This option requires positive integers as input values.

("1"*(Read-Host)-replace111,0-replace1).Length

Answer 30

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.

Answer 31

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.

Answer 32

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)]]

Answer 33

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.

Answer 34

Clojure, 87; works with negatives; based on lazyseqs

(defn d[n](def r(nth(apply interleave(repeat 3(range)))(Math/abs n)))(if(> n 0)r(- r)))

Ungolfed:

(defn d [n]
  (let [r (nth (->> (range) (repeat 3) (apply interleave))
               (Math/abs n))]
        (if (pos? n)
          r
          (- r))))

Answer 35

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

Answer 36

Sage Notebook (21)

ZZ(n.digits(3)[1:],3)

Answer 37

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).

Answer 38

05AB1E, 5 bytes (Non-competing)

3B¨3ö

Try it online!

Answer 39

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.

Answer 40

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(- %)%)))

Answer 41

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)... :-/

Answer 42

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. :)

Answer 43

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!

Answer 44

OCTAVE/MATLAB 13

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

length(1:3:x)

Answer 45

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!

Answer 46

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 ⁷/₃ . That fraction is then coerced to an Int. This should work for all ℤ .

Try it online!

Answer 47

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

Answer 48

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);}}

Answer 49

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 &div; 3 = n × (2⁶⁴ &div; 3) &div; 2⁶⁴

with an integer constant to approximate 2⁶⁴ &div; 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

• ⌊2⁶⁴ &div; 3⌋ = 5555 5555 5555 5555₁₆ if n is negative, or
• ⌈2⁶⁴ &div; 3⌉ = 5555 5555 5555 5556₁₆ 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.

Answer 50

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).

Answer 51

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

Answer 52

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

Answer 53

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.

Answer 54

perl 23

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

usage:

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

Doesn't work with negatives.

Answer 55

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*)

Answer 56

Ruby, 21 bytes

->n{3.step(n,3).size}

Try it online!

Answer 57

JavaScript (bitwise), 92 bytes

Because this is interview question, I assume they expected to see implementation of division using bitwise operations, not tricks with strings. So here it is. Works for negative values as well.

f=(a,b)=>b?f(a^b,(a&b)<<1):a
x=prompt(s=0)
while(y=x>>2)s=f(s,y),x=f(x&3,y)
alert(f(s,x==3))

Answer 58

Python 3, 29 chars

eval(str(x)+chr(47)*2+str(3))

first golf, feels cheaty to me but here goes!

other one for 44:

import numpy;print(int(numpy.mean([x,0,0])))

Answer 59

PHP, 66 bytes

<?='-'[$argn<=>0].intval(substr(base_convert($argn,10,3),0,-1),3);

Try it online!

Divides by lobbing off the least significant digit in the base 3 representation of the original number. The result is truncated (10/3 = 3), works with negative numbers and uses the PHP spaceship operator.

Answer 60

ReRegex, 22 bytes

a(_*)\1\1_*/$1/a#input

Takes IO in the form of unary _s via STDIN.

Simple program, matches three chunks of _'s as greedily as possible, and dumps out the first group. Remaining _'s are also matched away.

Try it online!

Answer 61

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.

Answer 62

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

Answer 63

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)\$

Answer 64

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.

Answer 65

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.

Answer 66

Scheme, 95 110 bytes

(define (h n)
  (length
   (let l ((a (iota n)))
     (if (> (length a) 2)
         (cons 1 (l (cdddr a)))
         '()))))

My original attempt using base conversion:

(define (g n)
  (string->number
   (list->string
    (reverse
     (cdr
      (reverse
       (string->list
        (number->string n 3))))))
   3))

I can't think of a better way of removing the last character from the string.