floyd_cycle_detection_algorithm.c File Reference

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

#include <assert.h>
#include <inttypes.h>
#include <stdio.h>

Include dependency graph for floyd_cycle_detection_algorithm.c:

Functions
uint32_t	duplicateNumber (const uint32_t *in_arr, size_t n)
	for assert
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()

uint32_t duplicateNumber	(	const uint32_t *	in_arr,
		size_t	n
	)

for assert

for uint32_t for IO operations

The main function implements the search algorithm

Template Parameters

T	type of array

Parameters

in_arr	the input array
n	size of the array

Returns

the duplicate number

< variable tortoise is used for the longer jumps in the array

< variable hare is used for shorter jumps in the array

{
    if (n <= 1) {  // to find duplicate in an array its size should be at least 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 {                                   // loop to enter the cycle
        tortoise = in_arr[tortoise];       // tortoise is moving by one step
        hare = in_arr[in_arr[hare]];       // hare is moving by two steps
    } while (tortoise != hare);
    tortoise = in_arr[0];
    while (tortoise != hare) {             // loop to find the entry point of cycle
        tortoise = in_arr[tortoise];
        hare = in_arr[hare];
    }
    return tortoise;
}

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 ( void  )

static

Self-test implementations.

Returns

void

{
    uint32_t arr[] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610}; // input array
    size_t n = sizeof(arr) / sizeof(int);
 
    printf("1st test... ");
    uint32_t index = duplicateNumber(arr, n); // calling the duplicateNumber function to check which number occurs twice in the array
    assert(index == 1); // the number which occurs twice is 1 or not
    printf("passed\n");
}

Here is the call graph for this function: