Kotlin Solution with Codility Example – Find The Smallest Positive Integer

Write a function:
fun solution(A: IntArray): Int
that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.
For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
Given A = [1, 2, 3], the function should return 4.
Given A = [−1, −3], the function should return 1.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [−1,000,000..1,000,000].

Solution using HashMap

– BigO = O(n)
Kotlin Coding:


import java.util.*

fun main() {
    var original: IntArray = intArrayOf(1, 2, 3)
    solution(original)
}

fun solution(A: IntArray): Int {
	if (A.size == 0)
		return 1
	
    var max = A[0]

    for (num in A) {
        if (max < num)
            max = num
    }


    var min = A[0]

    for (num in A) {
        if (min > num)
            min = num
    }

	if(max < 1) return 1
	if(min > 1) return 1
	
	var hashMap : HashMap<Int, Int> = HashMap<Int, Int> ()
	
	for ((index, value) in A.withIndex()) {
		hashMap.put(value , index)
	}
	
    val len = A.size - 1
    
	for (i in 1..len) {
		if(hashMap.get(i) == null){
			return i
        }
	}
	
	return A[A.size - 1] + 1
}

Solution 2 using Sorting

– BigO = O(nlg(n))

Kotlin Coding:


import java.util.*

fun main() {
    var original: IntArray = intArrayOf(4, 5, 3, -1, 11, -2, 1)
    println(solution(original))
}

fun solution(A: IntArray): Int {
	A.sort()	
	
	var indexPositiveStart = -1
	
	for((index, value) in A.withIndex()) {
		if (value > 0) {
			indexPositiveStart = index
			break
		}
	}
	if (indexPositiveStart == -1)
		return 1
	
	if(A[indexPositiveStart] > 1){
		return 1
	}
	
	for (i in indexPositiveStart until (A.size - 1)){
		// check next item
		if (i + 1 <= A.size - 1) {
			if (A[i] + 1 < A[i+1])
				return A[i] + 1
		}
	}
	
	return A[A.size - 1] + 1
}

Kotlin Count number of occurrences (or frequency) in a sorted array

Count number of occurrences (or frequency) in a sorted array
Expected time complexity is O(Logn)

– Example:


Input: arr[] = {1, 1, 2, 2, 2, 2, 3,},   x = 2
Output: 4 // x (or 2) occurs 4 times in arr[]

Solution -> Improved Binary Search
1) Use Binary search to get index of the first occurrence of x in arr[]. Let the index of the first occurrence be i.
2) Use Binary search to get index of the last occurrence of x in arr[]. Let the index of the last occurrence be j.
3) Return (j – i + 1);


import java.util.*

fun main() {
	var A = intArrayOf(1, 2, 2, 3, 4)
	println(solution(A, 2))
}

fun solution(A: IntArray, x: Int): Int {
	
	if (A.size == 0)
		return -1
	
	var leftOccur = binarySearchLeftMostOccurs(A, x, 0, A.size - 1)
	var rightOccur = leftOccur
	
	if (leftOccur == -1)
		return -1
	else {
		rightOccur = binarySearchRightMostOccurs(A, x, leftOccur, A.size - 1)
	} 
	
	return rightOccur - leftOccur + 1
}

fun binarySearchLeftMostOccurs(A: IntArray, x: Int, leftmost: Int, rightmost: Int): Int {

	if(leftmost == rightmost) {
		if (A[leftmost] == x) {
			return leftmost
		}
		
		return -1
	}
	
	var pivot = (leftmost + rightmost) / 2
	
	if(A[pivot] == x && ((pivot == leftmost) || (A[pivot - 1] < A[pivot]))) {
		return pivot
	}
	
	if(A[pivot] >= x){
		return binarySearchLeftMostOccurs(A, x, leftmost, pivot)
	}else {
		return binarySearchLeftMostOccurs(A, x, pivot + 1, rightmost)
	}
}

fun binarySearchRightMostOccurs(A: IntArray, x: Int, leftmost: Int, rightmost: Int): Int {
	if(leftmost == rightmost) {
		if (A[rightmost] == x) {
			return rightmost
		}
		
		return -1
	}
	
	var pivot = (leftmost + rightmost) / 2
	
	if(A[pivot] == x && ((pivot == rightmost) || (A[pivot] < A[pivot + 1]))) {
		return pivot
	}
	
	if(A[pivot] <= x){
		return binarySearchRightMostOccurs(A, x, pivot + 1, rightmost)
	}else {
		return binarySearchRightMostOccurs(A, x, leftmost, pivot)
	}
}

foreachindexed Kotlin Example

Tutorial “foreachindexed Kotlin Example”

In the tutorial, I will show you how to use Kotlin forEachIndexed method to loop through Kotlin Array, List, Map collections.

Kotlin foreachindexed method

forEachIndexed method performs the given action on each element, providing sequential index with the element.


inline fun <T> Array<out T>.forEachIndexed(
    action: (index: Int, T) -> Unit)
inline fun ByteArray.forEachIndexed(
    action: (index: Int, Byte) -> Unit)
inline fun ShortArray.forEachIndexed(
    action: (index: Int, Short) -> Unit)
inline fun IntArray.forEachIndexed(
    action: (index: Int, Int) -> Unit)
inline fun LongArray.forEachIndexed(
    action: (index: Int, Long) -> Unit)
inline fun FloatArray.forEachIndexed(
    action: (index: Int, Float) -> Unit)
inline fun DoubleArray.forEachIndexed(
    action: (index: Int, Double) -> Unit)
inline fun BooleanArray.forEachIndexed(
    action: (index: Int, Boolean) -> Unit)
inline fun CharArray.forEachIndexed(
    action: (index: Int, Char) -> Unit)
inline fun <T> Iterable<T>.forEachIndexed(
    action: (index: Int, T) -> Unit)
@ExperimentalUnsignedTypes inline fun UIntArray.forEachIndexed(
    action: (index: Int, UInt) -> Unit)
@ExperimentalUnsignedTypes inline fun ULongArray.forEachIndexed(
    action: (index: Int, ULong) -> Unit)
@ExperimentalUnsignedTypes inline fun UByteArray.forEachIndexed(
    action: (index: Int, UByte) -> Unit)
@ExperimentalUnsignedTypes inline fun UShortArray.forEachIndexed(
    action: (index: Int, UShort) -> Unit)

Performs the given action on each element, providing sequential index with the element.

Parameters: action – function that takes the index of an element and the element itself and performs the action on the element.

forEachIndexed Example with Array

Method Signature:

public inline fun <T> Array<out T>.forEachIndexed(action: (index: Int, T) -> Unit): Unit

Practice – foreachindexed Example with Array:


simpleArray.forEachIndexed{index, element -> println("index = $index, element = $element")}
// print on console
// ->
/*
  index = 0, element = 1
  index = 1, element = 2
  index = 2, element = 3
  index = 3, element = 4 
*/
customerArray.forEachIndexed{index, customer -> println("index = $index, customer = $customer")}
// print on console
// ->
/*
  index = 0, customer = Customer(name=Craig, age=45)
  index = 1, customer = Customer(name=Amos, age=23)
  index = 2, customer = Customer(name=Jack, age=20)
*/

foreachindexed Example with List

Method signature:

public inline fun <T> Iterable<T>.forEachIndexed(action: (index: Int, T) -> Unit): Unit

Practice – foreachindexed Kotlin Example with List:


simpleList.forEachIndexed{index, element -> println("index = $index, element = $element")}
// print on console
// ->
/*
  index = 0, element = 5
  index = 1, element = 6
  index = 2, element = 7
  index = 3, element = 8
*/
 
customerList.forEachIndexed{index, customer -> println("index = $index, customer = $customer")}
// print on console
// ->
/*
  index = 0, customer = Customer(name=Smith, age=26)
  index = 1, customer = Customer(name=Peter, age=43)
  index = 2, customer = Customer(name=Mary, age=27)
*/

Full Sourcecode

Here is the full sourcecode with the foreachindexed kotlin method. We create 2 data-structure: Kotlin Array and Kotlin List, then apply the foreachindexed method with the 2 collections in a main function.


package com.loizenai.kotlinforeach
 
data class Customer(
  val name: String,
  val age: Int
)
 
fun main(args : Array<String>) {
   
  val simpleArray = arrayOf(1, 2, 3,  4)  
  val customerArray = arrayOf(Customer("Craig", 45),
                  Customer("Amos", 23),
                  Customer("Jack", 20))
    
  // 1. work with Array
  println("-------------1. work with Array-------------")
  simpleArray.forEachIndexed{index, element -> println("index = $index, element = $element")}
  // print on console
  // ->
  /*
    index = 0, element = 1
    index = 1, element = 2
    index = 2, element = 3
    index = 3, element = 4 
   */
  customerArray.forEachIndexed{index, customer -> println("index = $index, customer = $customer")}
  // print on console
  // ->
  /*
    index = 0, customer = Customer(name=Craig, age=45)
    index = 1, customer = Customer(name=Amos, age=23)
    index = 2, customer = Customer(name=Jack, age=20)
   */
  
  // 2. work with List
  println("-------------2. work with List-------------")
  simpleList.forEachIndexed{index, element -> println("index = $index, element = $element")}
  // print on console
  // ->
  /*
    index = 0, element = 5
    index = 1, element = 6
    index = 2, element = 7
    index = 3, element = 8
   */
  
  customerList.forEachIndexed{index, customer -> println("index = $index, customer = $customer")}
  // print on console
  // ->
  /*
    index = 0, customer = Customer(name=Smith, age=26)
    index = 1, customer = Customer(name=Peter, age=43)
    index = 2, customer = Customer(name=Mary, age=27)
   */
}

Reference: foreachindexed Kotlin Method

Related Tutorial: