Find Duplicates in N+1 Array using Golang

In programming, there is a problem statement asked in interviews to find the duplicate number in an array of size N + 1. Also, there will be only one duplicate element in the array. The elements will be between 1 to N.

For example,

Array = {1,3,2,1,4}

1 is the duplicate element in the above array.

Algorithm

Step 1: Import the required packages at the top using the import keyword.

Step 2: Then the main function will get run first.

• First, we are declaring and initialize the array.

• Now, we are calling the function to find the duplicate element.

• In the end, we are printing the duplicate element.

Method 1

In this method, we are going to create a separate function in which we will run a nested for loop over the array and compare each element with others. Whenever we find the same elements we are returning the element and return from the function as well. The time complexity of this method is O(N*N) where N is the size of the array.

Example

This is the code to find the duplicate element in the array by running a nested loop over the array. On each iteration, we are checking if the element at index i is matching with the element at index j.

package main

import "fmt"

// function to print the array with array and
// size of the array as argument
func printArray(array []int, size int) {
    for i := 0; i < size; i++ {
        fmt.Print(array[i], " ")
    }
    fmt.Println()
}

func duplicateElement(array []int, size int) int {
    // running nested for loop to compare every element with each other
    for i := 0; i < size; i++ {
        for j := i + 1; j < size; j++ {
            // if the element at index i is equal to the element at index j
            //Then we are returning the duplicate element
            if array[i] == array[j] {
                return array[i]
            }
        }
    }
    return -1
}

func main() {
    // declaring and initializing the
    // array using the shorthand method
    array := []int{1, 5, 3, 2, 4, 5}

    fmt.Println("Golang program to find duplicate elements in an N+1 size array using nested for loop.")

    fmt.Print("array: ")
    printArray(array, len(array))

    // calling duplicateElement() function by passing array and length as the parameter
    duplicate := duplicateElement(array, len(array))

    fmt.Println(duplicate, "is a duplicate element in the array.")
}

Output

Golang program to find duplicate elements in an N+1 size array using nested for loop.
array: 1 5 3 2 4 5 
5 is a duplicate element in the array.

Method 2

In this method, in the separate function we are creating a map data structure. As you know in a map we can store the elements in the form of keys and values where values will be unique. In this case, the key will be of int type and the values will be of bool type. After creating a map we will iterate over the array by running a for loop and store the element by setting the value as true whenever we find that the value of the current element is already true in the map then we will return the value. The time complexity of this approach will be lesser than the previous one i.e. O(N) but the space complexity will increase as we are using the map.

Example

This is the code to find the duplicate element in the array by creating a map data structure and storing the elements in it and if the count becomes two we return that element.

package main

import "fmt"

// function to print the array with array and
// size of the array as argument
func printArray(array []int, size int) {
    for i := 0; i < size; i++ {
        fmt.Print(array[i], " ")
    }
    fmt.Println()
}

func duplicateElement(array []int, size int) int {
    // creating a map using the make function
    // where int is key and bool is value
    mapDuplicate := make(map[int]bool)

    // running for loop over the array
    for i := 0; i < size; i++ {
        // checking that array[i] is true or false in the map
        if mapDuplicate[array[i]] {
            return array[i]
        }
        mapDuplicate[array[i]] = true
    }
    return -1
}

func main() {
    // declaring and initializing the
    // array using the shorthand method
    array := []int{1, 5, 3, 2, 4, 5}

    fmt.Println("Golang program to find a duplicate element in an N+1 size array using the map data structure.")

    fmt.Print("array: ")
    printArray(array, len(array))

    // calling duplicateElement() function by passing array and length as the parameter
    duplicate := duplicateElement(array, len(array))

    fmt.Println(duplicate, "is a duplicate element in the array.")
}

Output

Golang program to find a duplicate element in an N+1 size array using the map data structure.
array: 1 5 3 2 4 5 
5 is a duplicate element in the array.

Method 3

This method will be better than both of the previous methods in terms of time and space both because here we are using the math formula of finding the sum of N numbers and then finding the sum of all the elements present in the array. In the end, the subtraction of the sum of all the elements and the sum of N numbers will return the value of the duplicate number. The time complexity will be O(N) where no space is used.

Example

This is the code to find the duplicate element in the array by using the maths formula of finding the sum of the array.

package main

import "fmt"

// function to print the array with array and
// size of the array as argument
func printArray(array []int, size int) {
    for i := 0; i < size; i++ {
        fmt.Print(array[i], " ")
    }
    fmt.Println()
}

func duplicateElement(array []int, size int) int {
    // declaring the variables using the var keyword
    var sum1, sum2 int

    sum1 = 0

    // using Maths formula to find the sum of N numbers
    sum2 = ((size - 1) * (size)) / 2
    // running for loop over the array
    for i := 0; i < size; i++ {
        // find the sum of all the elements of the array
        sum1 = sum1 + array[i]
    }

    // as the sum1 will more then sum2 which is equal to the extra element
    return sum1 - sum2
}

func main() {
    // declaring and initializing the
    // array using the shorthand method
    array := []int{1, 5, 3, 2, 4, 5}

    fmt.Println("Golang program to find duplicate elements in an N+1 size array using a math formula to find the sum of N numbers.")

    fmt.Print("array: ")
    printArray(array, len(array))

    // calling duplicateElement() function by passing array and length as the parameter
    duplicate := duplicateElement(array, len(array))

    fmt.Println(duplicate, "is a duplicate element in the array.")
}

Output

Golang program to find duplicate elements in an N+1 size array using a math formula to find the sum of N numbers.
array: 1 5 3 2 4 5 
5 is a duplicate element in the array.

Conclusion

These are three different methods to find the duplicate element in the array of N+1 elements where elements are from the set of 1 to N. Among all the three methods the third one is more efficient as we are using no extra space and O(N) time complexity. To learn more about Golang you can explore these tutorials.