Find the odd one out in a sequence

Question

The Challenge:

Consider the function F(N) = 2^N + 1 where N is a positive integer less than 31. The sequence defined by this function is:

3, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 2049, 4097, 8193, 16385, 32769, 65537, 131073, 262145, 524289, 1048577, 2097153, 4194305, 8388609, 16777217, 33554433, 67108865, 134217729, 268435457, 536870913, 1073741825

An input will be generated as follows:

• Take 5 contiguous integers from the above sequence.
• Replace one of them with a different, positive integer (which may or may not be part of the above sequence).
• Optionally reorder the the 5 resulting numbers.

Given such a list of 5 integers, find the one that was swapped in and is therefore not part of the original 5 contiguous integers.

Example:

• Original sublist: 5, 9, 17, 33, 65.
• Replace one: 5, 7, 17, 33, 65.
• Reorder: 33, 17, 5, 7, 65.

The expected output would be 7.

The 5 values in the input will always be distinct and there will always be a unique solution. (For instance, you won't have to deal with inputs like 3, 9, 17, 33, 129 where either 3 or 129 might have been swapped in.)

Test Cases:

5,9,17,33,829
o/p: 829

9,5,17,829,33
o/p: 829

33, 17, 5, 7, 65
o/p: 7

5,9,177,33,65
o/p: 177

65,129,259,513,1025
o/p: 259

129,259,513,1025,65
o/p: 259

63,129,257,513,1025
o/p: 63

65,129,257,513,4097
o/p: 4097

5, 9, 2, 17, 33
o/p: 2

536870913, 67108865, 1073741825, 1, 268435457
o/p: 1

Answer 1

Jelly, 15 bytes

⁹R2*‘ṡ5ḟ@€µEÐfQ

TryItOnline
All test cases also at TryItOnline

Returns a list containing one list containing the odd one out.

How?

⁹R2*‘ṡ5ḟ@€µEÐfQ - Main link, a (list)
⁹               - literal 256 (saving a byte over literal 30)
 R              - range, [1,2,3,...]
  2*            - 2 ** x, [2,4,8,...]
    ‘           - increment, [3,5,9,...]
     ṡ5         - all contiguous slices of length 5
       ḟ@€      - filter with reversed arguments for each
          µ     - monadic chain separation
            Ðf  - filter on condition:
           E    - all equal (those previously filtered lists with only one value)
              Q - unique (there can be two, but both will have the same odd-one-out)

Answer 2

JavaScript (ES6), 62 bytes

a=>a.find(n=>--n&--n|!n)||a.sort((a,b)=>a-b)[a[0]*16>a[3]?4:0]

Completely new algorithm, since as @edc65 pointed out the previous one was broken. Explanation: We first deal with the easy case by looking for a 2 or a number that is not one greater than a power of 2. If none was found then there are two possible cases, depending on whether the extra value was below or above the original run of five, so we check whether the smallest and second largest value belong to the same run of five and if so blame the largest value otherwise the smallest value.

Answer 3

Racket 198 bytes

(λ(m)(let((l(for/list((i(range 1 31)))(+ 1(expt 2 i))))(r 1)(n(length m)))(for((i(-(length l)n)))(let
((o(for/list((j m)#:unless(member j(take(drop l i)n)))j)))(when(eq?(length o)1)(set! r o))))r))

Ungolfed version:

(define f
  (λ(m)
    (let ((l (for/list ((i (range 1 31))) 
               (+ 1 (expt 2 i))))
          (res 1)
          (n (length m)))
      (for ((i (- (length l) n)))
        (let ((o (for/list ((j m) 
                             #:unless (member j 
                                             (take (drop l i) n))) 
                    j)))
          (when (eq? (length o) 1)
            (set! res o))))
      res)))

Testing:

(f '(5 9 17 33 829))
(f '(9 5 17 829 33))
(f '(5 9 177 33 65))
(f '(65 129 259 513 1025))
(f '(129 259 513 1025 65))
(f '(63 129 257 513 1025))
(f '(65 129 257 513 4097))

Output:

'(829)
'(829)
'(177)
'(259)
'(259)
'(63)
'(4097)

Answer 4

Python, 84 bytes

def f(a,i=0):s=set(a)-{2**j+1for j in range(i,i+5)};return len(s)<2and s or f(a,i+1)

All test cases are at ideone

For valid input returns a set containing only the odd-one-out.
For invalid input the recursion limit will be reached and an error will be thrown.

Answer 5

Mathematica, 65 bytes

f[a___,x_,b___]/;NestList[2#-1&,a~Min~b/. 2->0,4]~SubsetQ~{a,b}=x

This defines a function f which should be called with 5 arguments, e.g.

f[5, 9, 17, 33, 829]

In principle the function can be called with any (non-zero) number of arguments, but you might get unexpected results...

I think this is the first time, that I managed to put the entire solution to a non-trivial challenge into the left-hand side of a =.

Explanation

This solution really puts Mathematica's pattern matching capabilities to work for us. The basic feature we're using is that Mathematica can't just define simple functions like f[x_] := (* some expression in x *) but we can use arbitrarily complex patterns on the left-hand side, e.g. f[{a_, b_}, x_?OddQ] := ... would add a definition to f which is only used when it's called with a two-element list and an odd integer. Conveniently, we can already give names to elements arbitrarily far down the left-hand side expression (e.g. in the last example, we could immediately refer to the two list elements as a and b).

The pattern we're using in this challenge is f[a___,x_,b___]. Here a___ and b___ are sequences of zero or more arguments and x is a single argument. Since the right-hand side of the definition is simply x, what we want is some magic that ensures that x is used for the input we're searching for and a___ and b___ are simply wildcards that cover the remaining elements.

This is done by attaching a condition to the pattern with /;. The right-hand side of /; (everything up to the =) needs to return True for this pattern to match. The beauty is that Mathematica's pattern matcher will try every single assignment of a, x and b to the inputs for us, so the search for the correct element is done for us. This is essentially a declarative solution to the problem.

As for the condition itself:

NestList[2#-1&,a~Min~b/. 2->0,4]~SubsetQ~{a,b}

Notice that this doesn't depend on x at all. Instead, this condition depends only on the remaining four elements. This is another convenient feature of the pattern matching solution: due to the sequence patterns, a and b together contain all other inputs.

So this condition needs to check whether the remaining four elements are contiguous elements from our sequence with at most one gap. The basic idea for checking this is that we generate the next four elements from the minimum (via xi+1 = 2xi - 1) and check whether the four elements are a subset of this. The only inputs where that can cause trouble is those that contain a 2, because this also generates valid sequence elements, so we need to handle that separately.

Last part: let's go through the actual expression, because there's some more funny syntactic sugar here.

...a~Min~b...

This infix notation is short for Min[a,b]. But remember that a and b are sequences, so this actually expands to the four elements Min[i1, i2, i3, i4] and gives us the smallest remaining element in the input.

.../. 2->0

If this results in a 2, we replace it with a 0 (which will generate values which aren't in the sequence). The space is necessary because otherwise Mathematica parses the float literal .2.

NestList[...&,...,4]

We apply the unnamed function on the left 4 times to this value and collect the results in a list.

2#-1&

This simply multiplies its input by 2 and decrements it.

...~SubsetQ~{a,b}

And finally, we check that the list containing all elements from a and b is a subset of this.

Answer 6

05AB1E, 32 30 26 24 20 bytes

30Lo>Œ5ùv¹yvyK}Dgi`q

Explanation

30Lo>    # list containing the sequence [3 .. 1073741825]
Œ5ù      # all sequence sublists of length 5
v        # for each such list
 ¹yvyK}  # remove it's elements from input
 Dgi     # if the remaining list has length 1
    `q   # end the program and print the final list flattened

Try it online!

Answer 7

Haskell, 66 64 bytes

g x=[s|n<-[1..],[s]<-[filter(`notElem`[2^m+1|m<-[n..n+4]])x]]!!0

Usage example: g [65,129,257,513,4097] -> 4097.

Loops through all contiguous sublists of length 5 of F(N), keeps the elements that are not in the input list x and pattern matches those of length 1 (-> [s]).

Edit: @xnor saved two bytes by removing the upper bound of the outer loop. As a solution is guaranteed to exist, Haskell's laziness stops at the first number found.

Answer 8

R, 97 bytes

This turned out to be more difficult than I thought. I'm sure this can be golfed significantly though.

m=match(x<-sort(scan()),2^(1:31)+1);l=diff(m);ifelse(NA%in%m,x[is.na(m)],x[ifelse(l[4]>1,5,l>1)])

Ungolfed and explained

x<-sort(scan())                  # read input from stdin and sort, store as vector
m=match(x, 2^(1:31)+1)           # generate a vector of indices for which input matches the sequence
l=diff(m)                        # vector of the difference of indices (will only contain 4 elements)
ifelse(NA%in%m,                  # if m contains NA do:
       x[is.na(m)],              # return x where no match has been found, else:
       x[ifelse(l[4]>1,5,l>1)])  # return x by index where diff>1 unless it's the last object, then return x[5]

The match() function will return NA if the any element of the input vector is not in the sequence and consequently we can just find the index where NAexist in the input and return this: x[is.na(m)]

It gets a bit more complicated if input is part of the sequence but misplaced. Because input has been sorted, the distance between each pair of indices should be 1. We can therefore find the misplaced element by investigating the 1st difference of the matched indices l=diff(m) and select the index for which l>1. This would be just enough if it weren't for the fact that l contains 4 elements rather than 5. This is only a problem if the last element in the sorted input is a member of the sequence BUT not a part of the subsequence (as in the final test case). Consequently, if the 4th element >1 fetch the 5th entry in the sorted input else look for the index in the 4-length vector: x[ifelse(l[4]>1,5,l>1)]

Answer 9

Perl, 64 59 bytes

Includes +2 for -an

Give input list on STDIN:

perl -M5.010 oddout.pl <<< "5 9 2 17 33"

oddout.pl:

#!/usr/bin/perl -an
@a=grep$_,@a{@F,map{2**$_+++1}($.++)x5}=@F while$#a;say@a

If you don't mind variable amount of space around the result this 58 byte verson works:

#!/usr/bin/perl -ap
$_=join$",@a{@F,map{2**$_+++1}($.++)x5}=@F while/\b +\b/

Both versions loop forever if the input has no solution.

This is very sick code, but I can't think of anything elegant...

The way I (ab)use %a is a new perlgolf trick as far as I know.

Answer 10

PHP, 87 76 75 bytes

for(;count($b=array_diff($argv,$a?:[]))-2;)$a[$n%5]=1<<++$n|1;echo end($b);

run with php -r '<code>' <value1> <value2> <value3> <value4> <value5>

Answer 11

Python 2, 73 bytes

s=set(input());i,=d={1}
while~-len(s-d):i*=2;d=d-{i/32+1}|{i+1}
print s-d

Iterates through sets d of five consecutive sequence elements until it finds one that contains all but one of the input elements, and then prints the difference, which is the output in a singleton set.

The sets d of five consecutive elements are built up from nothing by repeatedly adding a new element i+1 and deleting any old element i/32+1 that comes before the current window of 5. Here's what its progress looks like.

{1}
{3}
{3, 5}
{3, 5, 9}
{3, 5, 9, 17}
{3, 5, 9, 17, 33}
{5, 9, 17, 33, 65}
{9, 17, 33, 65, 129}
{17, 33, 65, 129, 257}
{33, 65, 129, 257, 513}

There's a stray 1 at the start from initialization, but it's harmless because it's immediately removed. The smaller sets as it builds up to 5 elements are also harmless.

Answer 12

C#, 69 bytes

int M(int[]a)=>a.Except(new int[30].Select((_,i)=>(1<<i+1)+1)).Sum();

Answer 13

Java 7,85 bytes

int f(int[]a,int l){int i=1;for(;i<l;)if(a[i++-1]*2-1!=a[i])return a[i];return a[0];}

Ungolfed

int f(int[]a,int l){
    int i=1;
    for(;i<l;)
    if(a[i++-1]*2-1!=a[i])
    return a[i];
   return a[0];

}

Answer 14

PHP, 76 Bytes

implemented Titus idea with the mod 5

<?for(;count($x=array_diff($_GET[a],$r))-1;$r[++$i%5]=2**$i+1);echo end($x);

126 Bytes before

<?for(;$x=array_diff($_GET[a],array_map(function($z){return 2**$z+1;},range(++$i,$i+4)));)if(count($x)<2){echo end($x);break;}

Answer 15

Pyth, 18 bytes

hhlD-LQ.:mh^2dSCd5

Form the sequence, take sublists of length 5, Remove each sublist from Q, take the shortest result, output its only element.

Answer 16

Kotlin, 55 bytes

fun f(a:IntArray)=a.find{it-1 !in(1..30).map{1 shl it}}