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 :

Accumulator Pattern for beginners | Fold vs Reduce | AndroidBites
Accumulator pattern in kotlin | kotlin how to reduce | kotlin how to fold | reduce vs fold | best practice to reduce | transformation in kotlin | collection transformation | java vs koltin | java for loop anti patterns

Solution 2:

Using count

count - Kotlin Programming Language
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.

filter - Kotlin Programming Language
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.

groupingBy - Kotlin Programming Language
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

Solution 5:

using partition Β operator

partition - Kotlin Programming Language
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

single - Kotlin Programming Language
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! πŸ‘©β€πŸ’»

Solve Next:

BigBrainKotlin - The Morse Code 🀫
Don’t be a Java-ish dev in Kotlin-ish world, Morse code decode! let do it in Kotlinish way

Solve Previous:

BigBrainKotlin - Spin My Words
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 a lot!

Enjoy the Post?

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




Chetan gupta

Hi there! call me Ch8n, I'm a mobile technology enthusiast! love Android #kotlinAlltheWay, CodingMantra: #cleanCoder #TDD #SOLID #designpatterns

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.