floyd_cycle_detection_algo.cpp File Reference

Implementation of Floyd's Cycle Detection algorithm. More...

#include <cassert>
#include <iostream>
#include <vector>

Include dependency graph for floyd_cycle_detection_algo.cpp:

Namespaces
namespace	search
	for std::vector
namespace	cycle_detection
	Functions for the Floyd's Cycle Detection algorithm.

Functions
template<typename T >
int32_t	search::cycle_detection::duplicateNumber (const std::vector< T > &in_arr, const uint32_t &n)
	The main function implements search algorithm.
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Implementation of Floyd's Cycle Detection algorithm.

Given an array of integers containing 'n + 1' integers, where each integer is in the range [1, n] inclusive. If there is only one duplicate number in the input array, this algorithm returns the duplicate number in O(1) space and the time complexity is less than O(n^2) without modifying the original array, otherwise, it returns -1.

Author

Swastika Gupta

Function Documentation

duplicateNumber()

template<typename T >

int32_t search::cycle_detection::duplicateNumber	(	const std::vector< T > &	in_arr,
		const uint32_t &	n )

The main function implements search algorithm.

Template Parameters

T	type of array

Parameters

in_arr	the input array
n	size of array

Returns

the duplicate number

                                                                       {
    if (n == 0 ||
        n == 1) {  // to find duplicate in an array its size should be atleast 2
        return -1;
    }
    uint32_t tortoise = in_arr[0];  // variable tortoise is used for the longer
                                    // jumps in the array
    uint32_t hare =
        in_arr[0];  // variable hare is used for shorter jumps in the array
    do {
        tortoise = in_arr[tortoise];
        hare = in_arr[in_arr[hare]];
    } while (tortoise != hare);
    tortoise = in_arr[0];
    while (tortoise != hare) {
        tortoise = in_arr[tortoise];
        hare = in_arr[hare];
    }
    return tortoise;
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    test();  // run self-test implementations
    return 0;
}

Here is the call graph for this function:

test()

static void test ( )

static

Self-test implementations.

Returns

void

                   {
    // 1st test
    // [3, 4, 8, 5, 9, 1, 2, 6, 7, 4] return 4
    std::vector<uint32_t> array1 = {3, 4, 8, 5, 9, 1, 2, 6, 7, 4};
    std::cout << "Test 1... ";
    assert(search::cycle_detection::duplicateNumber(array1, array1.size()) ==
           4);  // here the duplicate number is 4
    std::cout << "passed" << std::endl;
 
    // 2nd test
    // [1, 2, 3, 4, 2] return 2
    std::vector<uint32_t> array2 = {1, 2, 3, 4, 2};
    std::cout << "Test 2... ";
    assert(search::cycle_detection::duplicateNumber(array2, array2.size()) ==
           2);  // here the duplicate number is 2
    std::cout << "passed" << std::endl;
 
    // 3rd test
    // [] return -1
    std::vector<uint32_t> array3 = {};
    std::cout << "Test 3... ";
    assert(search::cycle_detection::duplicateNumber(array3, array3.size()) ==
           -1);  // since the input array is empty no duplicate number exists in
                 // this case
    std::cout << "passed" << std::endl;
}

Here is the call graph for this function: