DEV Community

loading...

Discussion on: Coding Puzzles: Week of 4/8

Collapse
aspittel profile image
Ali Spittel Author

Tuesday (7 KYU): Find the stray number

codewars.com/kata/57f609022f4d534f...

Collapse
aspittel profile image
Ali Spittel Author
def stray(arr):
    for item in arr:
        if arr.count(item) == 1:
            return item
Collapse
joshuagilless profile image
Joshua Gilless

Thanks for this! I don't really know C++, but I figured I'd give it a shot:

int stray(std::vector<int> numbers) {
    int n1, n2, n3;
    for (int i = 2; i < numbers.size(); i++) {
      n1 = numbers[i];
      n2 = numbers[i - 1];
      n3 = numbers[i - 2];
      if (n1 == n2 && n1 != n3) {
        return n3;
      } else if (n1 == n3 && n1 != n2) {
        return n2;
      } else if (n1 != n2 && n2 == n3) {
        return n1;
      }
    }
};
Collapse
joshuagilless profile image
Joshua Gilless • Edited

@laurieontech did something really cool in JS with a bitwise XOR (her answer is above), so I figured I'd update this C++ answer with a bitwise XOR since I love it!

int stray(std::vector<int> numbers) {
    int r = numbers[0];
    for (int i = 1; i < numbers.size(); i++)
    {
        r ^= numbers[i];
    }
    return r;
};
Collapse
threeheadedcerb profile image
russ

Looks a bit messy, but I was going for something that might not be too inefficient with a large input array

def stray(arr):
    count = {}
    for index, i in enumerate(arr):
        count[i] = count.setdefault(i, 0) + 1
        if index >= 2 and len(count.keys()) > 1:
            break
    return next(k for k, v in count.items() if v == 1)
Collapse
jellebekker profile image
Jelle Bekker

in c# using linq:

public static int Stray(int[] numbers)
{
    return numbers.Aggregate((x, y) => x ^ y);
}

or:

public static int Stray(int[] numbers)
{
    return numbers.GroupBy(x => x).Single(num => num.Count() == 1).Key;
}
Collapse
ahmedmusallam profile image
Ahmed Musallam • Edited

here my cheap solution:

function stray(array) {
    var sorted = array.sort((a,b) => a - b)
    if (sorted[0] === sorted[1]) return sorted.pop();
    else return sorted.shift()
}

or shorter and more unreadable:

function stray(array) {
    var sorted = array.sort((a,b) => a - b)
    return sorted[0] === sorted[1] ? sorted.pop() : sorted.shift();
}

Collapse
clandau profile image
Courtney • Edited

This is the first I'm finding this, excited to play along! Here is yesterday's (edited to make the colors show up):

function stray(numbers) {
  let num1 = numbers[0], num2;
  let dupOf1 = false;
  for(let i=1; i<numbers.length; i++) {
      if(numbers[i] === num1) {
        if(num2) return num2;
        else dupOf1 = true;
      }
      else if(numbers[i] === num2) return num1;
      else num2 = numbers[i];
    }
  return dupOf1 ? num2 : num1;
}
Collapse
jacobmgevans profile image
Jacob Evans • Edited

I don't think this is better than the bitwise solution but it's a different one lol

const stray =(n)=> n.filter((ele,_,ar) => ele !== ar[1]).pop()
Collapse
laurieontech profile image
Laurie
function stray(arr) {
    return arr.reduce((a, b) => a ^ b)
}
Collapse
joshuagilless profile image
Joshua Gilless

XOR is a great idea, thanks!

Thread Thread
laurieontech profile image
Laurie

Math for the win! :D

Collapse
jacobmgevans profile image
Jacob Evans

Well I can't think of a better answer for this particular problem domain.

Collapse
threeheadedcerb profile image
russ

What is this necromancy?

Thread Thread
laurieontech profile image
Laurie • Edited

Haha, bitwise xor. Since it's immutable and commutative it'll reduce down to the stray!

I should add that this only works because it’s an odd number of elements in the array. An even number of matching elements cancel each other out to result in the “stray”.

Thread Thread
threeheadedcerb profile image
russ

Oh my, it even works in python!

def stray(arr):
    count = {}
    for index, i in enumerate(arr):
        count[i] = count.setdefault(i, 0) + 1
        if index >= 2 and len(count.keys()) > 1:
            break
    return next(k for k, v in count.items() if v == 1)

from functools import reduce

def intstray(arr: [int]):
    return reduce(lambda x,y: x ^ y, arr)

assert(intstray([1, 1, 2]) == 2)
#nope..!
#assert(intstray([1, 1, 2, 1]) == 2)
assert(intstray([17, 17, 3, 17, 17, 17, 17]) == 3)
assert(intstray([1, 2, 2]) == 1)
assert(stray(["bob", "bob", "bob", "steve", "bob"]) == "steve")
Thread Thread
laurieontech profile image
Laurie

This is one of those moments when I wish gifs worked better on Dev. But yay!

Thread Thread
aspittel profile image
Ali Spittel Author

They should work in normal image markdown!

Thread Thread
laurieontech profile image
Laurie

Whaaa?! How did I not know this! ...game changer

Collapse
mihassan profile image
Md Imrul Hassan

Same idea in Haskell:

import Data.Bits

stray :: [Int] -> Int
stray = foldl1 xor