BBK#5: Imposter Among Us...

problemsolving Nov 27, 2020

Don't be a Java-ish dev in Kotlin-ish world, improve your knowledge about Koltin Standard Library and write better Kotlin code. ✌🏻 If your Java dev migrating to Kotlin this will help you learn alot!

Question: Find the imposter from the given array with atleast 3 items, it's either entirely comprised of odd integers or entirely comprised of even integers except for a single integer N. Write a method that takes the array as an argument and returns this "Imposter" N. .

imposter(arrayOf(2,6,8,-10,3)) => returns 3

imposter(arrayOf(206847684,1056521,7,17,1901,21104421,7,1,35521,1,7781)) => returns 206847684

imposter(arrayOf(Integer.MAX_VALUE, 0, 1))=> returns 0

Try it put yourself :
👨🏻‍💻👉 https://www.codewars.com/kata/5667e8f4e3f572a8f2000039/train/kotlin

This problem is awesome, cause It has multiple ways to implement it. I will highly recommend giving it as shot and figure out all the ways. Anyways lets start ...

Solution 1:

fun imposter(integers: Array<Int>): Int {
    // convert array to 0,1
    val flattened = integers.map{Math.abs(it%2)}
    // count numbers of 0 and 1
    val (zeroCount,oneCount) = flattened.take(3)
    	.fold(0 to 0){ acc, item->
            return@fold when{
                item == 0 -> acc.copy(first = acc.first+1)
                else -> acc.copy(second = acc.second+1)
            }
    }
    // if array of 1's find 0, else find 1
    val whoIsImposer = if(oneCount > zeroCount) 0 else 1
    val imposterIndex = flattened.indexOf(whoIsImposer)
    return if(imposterIndex!=-1)integers[imposterIndex] else -1
}

// complexity: O(3n+2) ~ O(n) 
// Performance : took 11.7 ms on my machine

Learn fold and reduce like a boss, checkout :

Solution 2:

Using count

fun imposter(integers: Array<Int>): Int {
        // convert to 0 and 1
        val flatten =integers.map{
            kotlin.math.abs(it % 2)
        }
        // count 0
        val odd = flatten.count { it == 0 }
        // count 1
        val even = flatten.count { it == 1 }
        
        // find and return index
       return if(odd > even){
       	integers[flatten.indexOf(1)] 
       } else {
       	integers[flatten.indexOf(0)]
       }
    }
    
// complexity : O(4n+2) ~ O(n)
// Performance : took 12.71 ms on my machine

Solution 3:

using filter operator.

fun imposter(integers: Array<Int>): Int {
    // filter that pass even numbers
    val evens = integers.filter { it % 2 == 0 }
    // filter that pass odd numbers
    val odds = integers.filter { it % 2 != 0 }
    
    // which ever has size 1, print its first element
    return if(evens.size == 1){
        evens.first()
    }else{
        odds.first()
    }
}

// complexity: O(2n+1) ~ O(n) 
// Performance : took 9.19 ms on my machine

Solution 4:

using groupby operator.

fun imposter(integers: Array<Int>): Int =
    integers.groupBy { it % 2 == 0 } // convert to map with even-odd
    	.values // list of map values
        .first { it.size == 1 } // get first whose size is 1
        .first() // get the first item

// complexity: O(n+1) ~ O(n) 
// Performance : took 9.27 ms  on my machine

Enjoying the Post?

a clap is much appreciated if you enjoyed. No sign up or cost associated :)

If you want to support my content do consider dropping a tip/coffee/donation💰

Solution 5:

using partition operator

fun imposterC3(integers: Array<Int>): Int {
	// break into list of two items of even/odd
  val (even, odd) = integers.partition { it % 2 == 0 } 
  return if (even.size == 1) even[0] else odd[0]
}

// complexity: O(n+1) ~ O(n) 
// Performance : took 2.97 ms  on my machine

Solution 6:

using Single and SingleOrNull operator

fun imposter(integers: Array<Int>) = with(integers){
   // find odd if null find even
   singleOrNull { it % 2 == 0 } ?: single { it % 2 != 0 }
}

// complexity : best => O(n), worse=> O(2n) ~ O(n)
// Performance : took 2.96 ms on my machine

Conclusion

Aim of these articles is not hate on Java, but to help people learn various ways in which they can write same logic better and more Kotlin standard library focused way.

Hope you find it informative and if you have any feedback or post request or want to subscribe to my mailing list forms are below.

Until next time. Happy Hacking! 👩‍💻