TheAlgorithms/C++
1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
floyd_cycle_detection_algo.cpp
Go to the documentation of this file.
1
13
14
#include <cassert>
15
#include <cstdint>
16
#include <iostream>
17
#include <vector>
22
namespace
search
{
28
namespace
cycle_detection
{
36
template
<
typename
T>
37
int32_t
duplicateNumber
(
const
std::vector<T> &in_arr,
const
uint32_t &n) {
38
if
(n == 0 ||
39
n == 1) {
// to find duplicate in an array its size should be atleast 2
40
return
-1;
41
}
42
uint32_t tortoise = in_arr[0];
// variable tortoise is used for the longer
43
// jumps in the array
44
uint32_t hare =
45
in_arr[0];
// variable hare is used for shorter jumps in the array
46
do
{
47
tortoise = in_arr[tortoise];
48
hare = in_arr[in_arr[hare]];
49
}
while
(tortoise != hare);
50
tortoise = in_arr[0];
51
while
(tortoise != hare) {
52
tortoise = in_arr[tortoise];
53
hare = in_arr[hare];
54
}
55
return
tortoise;
56
}
57
}
// namespace cycle_detection
58
}
// namespace search
59
64
static
void
test
() {
65
// 1st test
66
// [3, 4, 8, 5, 9, 1, 2, 6, 7, 4] return 4
67
std::vector<uint32_t> array1 = {3, 4, 8, 5, 9, 1, 2, 6, 7, 4};
68
std::cout <<
"Test 1... "
;
69
assert(
search::cycle_detection::duplicateNumber
(array1, array1.size()) ==
70
4);
// here the duplicate number is 4
71
std::cout <<
"passed"
<< std::endl;
72
73
// 2nd test
74
// [1, 2, 3, 4, 2] return 2
75
std::vector<uint32_t> array2 = {1, 2, 3, 4, 2};
76
std::cout <<
"Test 2... "
;
77
assert(
search::cycle_detection::duplicateNumber
(array2, array2.size()) ==
78
2);
// here the duplicate number is 2
79
std::cout <<
"passed"
<< std::endl;
80
81
// 3rd test
82
// [] return -1
83
std::vector<uint32_t> array3 = {};
84
std::cout <<
"Test 3... "
;
85
assert(
search::cycle_detection::duplicateNumber
(array3, array3.size()) ==
86
-1);
// since the input array is empty no duplicate number exists in
87
// this case
88
std::cout <<
"passed"
<< std::endl;
89
}
90
95
int
main
() {
96
test
();
// run self-test implementations
97
return
0;
98
}
search::cycle_detection::duplicateNumber
int32_t duplicateNumber(const std::vector< T > &in_arr, const uint32_t &n)
The main function implements search algorithm.
Definition
floyd_cycle_detection_algo.cpp:37
test
static void test()
Self-test implementations.
Definition
floyd_cycle_detection_algo.cpp:64
main
int main()
Main function.
Definition
floyd_cycle_detection_algo.cpp:95
cycle_detection
Functions for the Floyd's Cycle Detection algorithm.
search
for std::assert
Definition
binary_search.cpp:47
search
floyd_cycle_detection_algo.cpp
Generated by
1.13.2