20
\$\begingroup\$

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
\$\endgroup\$
  • 4
    \$\begingroup\$ For future reference, confusion and misunderstandings like this can often be avoided by posting challenge ideas in the sandbox first, where you can get feedback from the community before people start solving your challenge. \$\endgroup\$ – Martin Ender Sep 27 '16 at 7:53
  • \$\begingroup\$ @Ajay Since there was still some confusion about the specification I have edited the challenge once more with what I think was your intent behind this challenge. I hope I didn't misinterpret it, but do let me know if I got anything wrong. \$\endgroup\$ – Martin Ender Sep 27 '16 at 16:59
  • \$\begingroup\$ @MartinEnder the new test case should be 536870913,67108865,134217729,1,268435457 \$\endgroup\$ – Jörg Hülsermann Sep 27 '16 at 17:19
  • \$\begingroup\$ @JörgHülsermann Feel free to add that as well, but my intention was to add a test case that covers N = 30 as one of the input values. \$\endgroup\$ – Martin Ender Sep 27 '16 at 17:26
  • 1
    \$\begingroup\$ An interesting challenge because it's so easy to come up with wrong algorithms. And indeed I've never seen so many incorrect answers posted. It would have been even worse if duplicates were allowed (many set based methods (including mine) would fail) \$\endgroup\$ – Ton Hospel Sep 28 '16 at 8:52

16 Answers 16

6
\$\begingroup\$

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)
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Almost ok but try n-1&n-2 with the value 2 \$\endgroup\$ – edc65 Sep 28 '16 at 10:11
  • \$\begingroup\$ @edc65 Doesn't work for [3, 17, 33, 65, 257]. \$\endgroup\$ – Neil Sep 28 '16 at 10:46
  • \$\begingroup\$ @edc65 Does --n&--n|!n look good for the 2 case? \$\endgroup\$ – Neil Sep 28 '16 at 10:48
  • \$\begingroup\$ It looks good indeed \$\endgroup\$ – edc65 Sep 28 '16 at 12:50
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I didn't know Mathematica could do this! \$\endgroup\$ – DanTheMan Sep 28 '16 at 5:17
4
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ in recent versions of R there is a function anyNA which is equivalent to any(is.na(x)) \$\endgroup\$ – JDL Sep 28 '16 at 11:51
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Do you actually need the upper bound of 26? \$\endgroup\$ – xnor Sep 28 '16 at 8:05
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ 'a=[]` is not neccessary \$\endgroup\$ – Jörg Hülsermann Sep 28 '16 at 7:33
  • \$\begingroup\$ @JörgHülsermann: It is necessary for array_diff. But I can save one byte there. \$\endgroup\$ – Titus Sep 28 '16 at 7:56
  • \$\begingroup\$ It results in a warning array_diff(): Argument #2 is not an array. Nice way with fill the array with the mod 5. It will save me array_map and range in my proposal \$\endgroup\$ – Jörg Hülsermann Sep 28 '16 at 8:05
  • 1
    \$\begingroup\$ end instead of max and your note is no more important \$\endgroup\$ – Jörg Hülsermann Sep 28 '16 at 8:31
1
\$\begingroup\$

C#, 69 bytes

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

\$\endgroup\$
0
\$\begingroup\$

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

}
\$\endgroup\$
  • \$\begingroup\$ Hmm, are you sure this works correctly? Because I'm getting an incorrect output for the test cases 1, 5, 6, and 7 (only the second, third and fourth output are correct). Also, is the parameter l 31? In the question I only see an int-array as input, but not an additional int? :S \$\endgroup\$ – Kevin Cruijssen Sep 27 '16 at 12:21
  • \$\begingroup\$ Won't this fail if the odd value out is the second one (at index 1) ? \$\endgroup\$ – Ton Hospel Sep 27 '16 at 12:40
  • \$\begingroup\$ Sorry guys,I misinterpret the question.. Actually now I am in hospital.. I ll change it in a short span of time. \$\endgroup\$ – Numberknot Sep 27 '16 at 15:27
0
\$\begingroup\$

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;}
\$\endgroup\$
  • \$\begingroup\$ anonymous function: array_map(function($z){return 2**$z+1;},range($i,$i+4)). $x[key($x)] --> end($x) \$\endgroup\$ – Titus Sep 27 '16 at 23:33
  • \$\begingroup\$ Putting 1-count($x=...) to the condition will get you rid of the break: for(;1-count($x=...););echo end($x); (-13) \$\endgroup\$ – Titus Sep 28 '16 at 8:14
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Doesn't work for [5, 9, 2, 17, 33] \$\endgroup\$ – Emigna Sep 27 '16 at 20:42
0
\$\begingroup\$

Kotlin, 55 bytes

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

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