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

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

Sage Notebook (21)

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

Answer 2

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 3

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 4

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 5

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 6

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 7

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 8

05AB1E, 5 bytes

3B¨3ö

Try it online!

Answer 9

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 10

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 11

OCTAVE/MATLAB 13

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

length(1:3:x)

Answer 12

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 13

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 14

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 × (2⁶⁴ ÷ 3) ÷ 2⁶⁴

with an integer constant to approximate 2⁶⁴ ÷ 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⁶⁴ ÷ 3⌋ = 5555 5555 5555 5555₁₆ if n is negative, or
• ⌈2⁶⁴ ÷ 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 15

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 16

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 17

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 18

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 19

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 20

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 21

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 22

Jelly, 5 bytes

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 23

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 24

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 25

perl 23

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

usage:

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

Doesn't work with negatives.

Answer 26

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 27

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 28

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 29

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 30

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.