Having a vector V with (N-1) numbers with values from 1 to N find the number X that is missing which value is between 1 and N.
Solution1 - Low Efficiency - O(n*n)
Take every number from 1 to N and search it if it's in the vector number.
Solution2 - O(n*logn)Sort the number first and then check if V[i] != i.
Solution3- O(n)Using "Divide et Impera" algorithm to split the vector in 2 sub-vectors having size of maximum N/2 (first vector will have all the elements smaller or equal with N/2 and the second vector will have all the elements bigger than N/2). After every split you can find in which sub-vector is the missing number because will have a small number of elements.
Solution4 - The Smart One- O(n) time, O(1) spaceUsing the property of SUM(1..N) = N*(N+1)/2, the element
X that is missing can be find by:
X = SUM(1..N) - SUM(V's elements).
Sithonia is the middle peninsula of Halkidiki and its beauty is similar to that of the Kassandra peninsula. While on a tour in Sithonia you can admire endless majestic landscapes, picturesque little harbors, wonderful golden beaches, secluded bays next to olive plantations, lovely meadows and deep green forests, peaceful fishers' villages and also the amazing architecture of houses and churches. Only in Halkidiki you can admire glorious beaches with the perfect combination of green and blue as when the wind gently blows the pine trees meet the waves.
Sighisoara - Founded by German craftsmen and merchants known as the Saxons of Transylvania, Sighisoara is a fine example of a small, fortified medieval town which played an important strategic and commercial role on the fringes of central Europe for several centuries.
Sights
