Find algorithm task

Pages: 12
frek (576)
The exercise says:
https://imgur.com/a/Zm7Q8hx

And here's my first solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
#include <iostream>
#include <vector>
#include <algorithm>

bool solution(std::vector<int>& vd) {

	if (!vd.size()) return false;
	auto t = vd.begin();
	std::vector<int> vp; // vector of exclusive pairs

	for (size_t i = 0; i < vd.size(); ++i)
		if (vp.empty() || std::find(vp.begin(), vp.end(), vd[i]) == vp.end()) {
			vp.push_back(vd[i]);
			if (std::count(t++, vd.end(), vd[i]) != 2)
				return false;
		}
	return true;
}

int main() {

	std::vector vd { 5, 5, 1, 1 };
	std::cout << solution(vd) << '\n';

	return 0;
}

Any comments?
Last edited on
keskiverto (10402)
That does not compile; error on line 22.

What do you get with { 5, 5, 5, 5 } and why?


What if N==99999 -- are you "efficient"?
Last edited on
seeplus (6591)
L22 requires at least C++17.
seeplus (6591)
It may not be the most efficient, but one way is to use a map of key number with value the number of times that number specified. For all numbers to be matched, all the values would need to be even.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

bool solution(const std::vector<int>& vd) {
	std::map<int, size_t> cnt;

	for (const auto& v : vd)
		++cnt[v];

	for (const auto& [num, val] : cnt)
		if (val % 2)
			return false;

	return true;
}

int main() {
	const std::vector vd {1,2,3,4,4,3,2,1};

	std::cout << solution(vd) << '\n';
}

lastchance (6980)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#include <iostream>
#include <vector>
#include <set>
using namespace std;

bool solution( vector<int>& vd )
{
   if ( vd.size() % 2 ) return false;   // Can't possibly "pair-up"
   
   set<int> S;
   for ( int e : vd ) if ( !S.insert( e ).second ) S.erase( e );
   return S.empty();
}

int main()
{
   vector< vector<int> > tests = { { 1, 2, 2, 1 }, { 7, 7, 7 }, { 1, 2, 2, 3 }, {} };
   for ( auto &vd : tests ) cout << boolalpha << solution( vd ) << '\n';
}
coder777 (8444)
One simple approach might be:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
#include <iostream>
#include <vector>
#include <algorithm>

bool solution(std::vector<int>& vd)
{

  if(vd.size() % 2) return false;

  auto it_end = vd.begin() + vd.size();
  while(it_end != vd.begin())
  {
    auto it = std::find(vd.begin() + 1, it_end, vd.front());
    if(it != it_end)
    {
      --it_end;
      std::swap(vd.front(), *it_end);
      --it_end;
      std::swap(*it, *it_end);
    }
    else
      return false;
  }

  return true;
}

int main()
{

  std::vector<int> vd{5, 5, 1, 1, 3, 4};
  std::cout << solution(vd) << '\n';

  return 0;
}
seeplus (6591)
This is why I only scraped a pass in the degree algorithm course - and was advised against taking the advanced algorithm course, Luckily my grades in the other courses made up for this!
frek (576)
Great use of stl containers std::map and std::set (especially set), thanks.

About another exercise simply said:
Rotate an array to the right by a given number of steps.
with the following function declaration: std::vector<int> solution(std::vector<int>& A, int K)
I wrote solutions #1 and #2 as following, both correct.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
std::vector<int> solution(std::vector<int>& A, int K) {

	if (A.size() == 0 || K == 0 || K == A.size())
		return A;
        while (K-- > 0) {
	/*	for (int i = A.size() - 1; i > 0; --i)
		  std::swap(A[i], A[i - 1]); */            #1


	/*	A.insert(A.begin(), A.back());
		A.pop_back();  */                        #2
	}
	return A;
}


#2 looks much better in terms of time complexity even though I'm not sure if we look at what's going on under the hood this idea will change or not.
Last edited on
deleted account xyzzy (5768)
std::rotate works wonders. :)

https://en.cppreference.com/w/cpp/algorithm/rotate

Note the complexity of the C++ library algorithm, along with a possible implementation.
lastchance (6980)
The function signature implies that you DON'T rotate in place. You create a new vector and COPY two segments of the original vector (the last k elements, then the rest) into it.
frek (576)
@George:
1
2
3
 
template <class ForwardIterator>
  ForwardIterator rotate (ForwardIterator first, ForwardIterator middle,
                          ForwardIterator last);

Can it rotate all elements from beginning to the end (not from the middle)?

@lastchance
The function signature implies that you DON'T rotate in place. You create a new vector and COPY two segments of the original vector (the last k elements, then the rest) into it.
1) How is that implication stated in the function signature, please?
2) Yes, I could use of a temporary vector but found it redundant considering the two solutions offered.
3) What's their time complexity to you please? (I mean solutions I offered)
lastchance (6980)
@frek,
(1) Your function signature says that you are going to return a vector. If you were going to rotate in place you could just have had a void function.
(2) You've created a new vector anyway in returning it.
(3) Your solutions have time complexity NK (though some of it will be hidden in a standard library call). You shouldn't have to do K loops even if you were rotating in place.

A copy arrangement of two segments would have time complexity N, as would use of std::rotate().
Last edited on
frek (576)
You mean something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
std::vector<int> solution(std::vector<int>& A, int K) {

	if (A.size() == 0 || K == 0 || K == A.size()) 
		return A;

	if (K > A.size()) K %= A.size();

	std::vector<int> res;

	for (int i = 0; i < A.size(); ++i)
		if (i >= K - 1)
			res.push_back(A[i]);

	for (int i = 0; i < A.size(); ++i)
		if (i < K - 1)
			res.push_back(A[i]);

    return res;
}


Do you use any tool to measure the efficiency and correctness of your algorithms, please?
deleted account xyzzy (5768)
Can it rotate all elements from beginning to the end (not from the middle)?
ForwardIterator middle is the element that should appear at the beginning of the rotated range. Think: offset.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
#include <vector>
#include <iostream>
#include <algorithm>

int main()
{
   std::vector<int> v { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

   std::cout << "before rotate:\t";
   for (const auto& itr : v)
   {
      std::cout << itr << ' ';
   }
   std::cout << '\n';

   std::rotate(v.begin(), v.begin() + 4, v.end());

   std::cout << "rotate left:\t";
   for (const auto& itr : v)
   {
      std::cout << itr << ' ';
   }
   std::cout << "\n\n";

   v = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

   std::cout << "before rotate:\t";
   for (const auto& itr : v)
   {
      std::cout << itr << ' ';
   }
   std::cout << '\n';

   std::rotate(v.rbegin(), v.rbegin() + 4, v.rend());

   std::cout << "rotate right:\t";
   for (const auto& itr : v)
   {
      std::cout << itr << ' ';
   }
   std::cout << '\n';
}
before rotate:  1 2 3 4 5 6 7 8 9
rotate left:    5 6 7 8 9 1 2 3 4

before rotate:  1 2 3 4 5 6 7 8 9
rotate right:   6 7 8 9 1 2 3 4 5
std::rotate can transform the entire container, though it is possible to rotate only a part of the container.
Chane line 16 to std::rotate(v.begin() + 2, v.begin() + 4, v.end() - 2);
before rotate:  1 2 3 4 5 6 7 8 9
rotate left:    1 2 5 6 7 3 4 8 9

An insertion sort using std::rotate works on a subset range repeatedly until the elements are sorted. The example at cppreference show how that is done.

std::ranges::rotate is IMO a bit more intuitive with left and right shifting via an offset.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

int main()
{
   std::string s(16, ' ');

   std::iota(s.begin(), s.end(), 'A');
   std::cout << "Before rotate:\t" << s << '\n';
   std::ranges::rotate(s, s.begin() + 5);
   std::cout << "Rotate left:\t" << s << "\n\n";

   std::iota(s.begin(), s.end(), 'A');
   std::cout << "Before rotate:\t" << s << '\n';
   std::ranges::rotate(s, s.end() - 5);
   std::cout << "Rotate right:\t" << s << '\n';
}
Before rotate:  ABCDEFGHIJKLMNOP
Rotate left:    FGHIJKLMNOPABCDE

Before rotate:  ABCDEFGHIJKLMNOP
Rotate right:   LMNOPABCDEFGHIJK
<ranges> requires C++20 or later.
https://en.cppreference.com/w/cpp/algorithm/ranges/rotate
Duthomhas (13206)
TASK 1 • INTEGER PAIRS

I can think of an easy O(n log n + n) solution (sort), and an also easy O(2n) solution (histogram). You really aren’t going to get better than this. seeplus and lastchance nailed this one. (Sorry coder777, that’s an O(n²) solution.)

TASK 2 • ROTATE RIGHT K ELEMENTS

The function signature is confused. It takes a mutable reference to a vector and returns a new vector? It should be either:

  • std::vector<int>   rotate_right( const std::vector<int> & A, int K );
  • std::vector<int> & rotate_right(       std::vector<int> & A, int K ); // or return void

The consequence is significant, because the first implies (as lastchance stated) that the rotation is accomplished via a simple copy, while the second requires more careful thinking (assuming we wish to perform the rotate in-place). As-is it kind of implies... both?

@frek
All your solutions are O(NK) == O(n²).
Remember, you need to work with a solution before you jump into programming it. Pick something small you can work with (arrays of 5 and 6 elements are a good start) and see what patterns you can find as you play with them. Sometimes it just takes attacking it from different angles until things make sense.

I haven’t looked at how std::rotate() does things for a long, long time. But assuming an in-place rotate and assuming I am not allowed to use std::rotate(), this is how I would do it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
// cl /EHsc /W4 /Ox /std:c++17 -Ddebug a.cpp
// clang++ -Wall -Wextra -pedantic-errors -O3 -std=c++17 -Ddebug a.cpp


#include <ciso646>
#include <utility>
#include <vector>

#ifndef debug
  #define debug(...)
#else
  #undef debug
  #define debug(...) __VA_ARGS__  
#endif

debug( int SWAP_COUNT = 0; )


namespace internal
{
  int fix_K( int K, int N )
  {
    if (K < 0) return N - (-K % N);
    else       return       K % N;
  }
  
  std::vector<int> & rotate_right( std::vector<int> & A, int K, int N )
  {
    using std::swap;
    if ((K == 0) or (N < 2)) return A;
    int a = 0;
    int b = K;
    while (b < N)
    {
debug( SWAP_COUNT += 1; )
      swap( A[a], A[b] );
      a = (a + 1) % K;
      b =  b + 1;
    }
    return rotate_right( A, fix_K( K-N, K ), K );  // tailcall recursion :O)
  }
}

std::vector<int> & rotate_right( std::vector<int> & A, int K )
{
  // N ← A.size(); N > 0
  int N = (int)A.size();
  if (!N) return A;
  
  // K ← number of elements to shift right; 0 ≤ K < N
  K = internal::fix_K( K, N );
  
  return internal::rotate_right( A, K, N );
}


#include <iostream>
#include <numeric>

int main()
{
  for (int N = 0;  N < 11;  N++)
  {
    std::cout << "\nN = " << N << "\n";
    for (int K = -N;  K < N;  K++)
    {
debug( SWAP_COUNT = 0; )
      std::vector<int> xs( N, 0 );  std::iota( xs.begin(), xs.end(), 0 );
      std::cout << "K = " << K << ":";
      for (int x : rotate_right( xs, K )) std::cout << " " << x;
debug( std::cout << "  (" << SWAP_COUNT << " swaps)"; )
      std::cout << "\n";
    }
  }
}

This is an O(n) in-line solution requiring O(1) extra space (for the swap).
frek (576)
A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the elements at indexes 0 and 2 have value 9,
the elements at indexes 1 and 3 have value 3,
the elements at indexes 4 and 6 have value 9,
the element at index 5 has value 7 and is unpaired.
Write a function:

int solution(vector<int> &A);

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

N is an odd integer within the range [1..1,000,000];
each element of array A is an integer within the range [1..1,000,000,000];
all but one of the values in A occur an even number of times.

I wrote these two solutions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
int solution(std::vector<int>& A) {

/*	std::set<int> mySet;
	for (int i = 0; i < A.size(); ++i)
		if (!(mySet.insert(A[i]).second)) mySet.erase(A[i]);      solution #1
	return *mySet.begin(); */

   /*	std::sort(A.begin(), A.end());
	int temp{ -1 };

	for (int i = 0; i < A.size(); ++i) {
		if (A[i] != temp)                                        solution #2
			temp = A[i];                                     
		if (i + 1 < A.size() && A[i + 1] == temp) {
			temp = -1;
			++i;
		}
		else return A[i];
	} */
}


#1 has time complexity likely equal to N^2, and #2 O(N) or O(N log N).

Do you have a better solution (but not as complex as Duthomhas'! :)
leo2008 (147)
Sort it this way, this is much better solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
int solution(vector<int> &A) {

    if(A.size() == 1){
        return A[0];
    }
    // sort this way
    sort(A.begin(), A.end());
    
    for(int k=0; k<A.size(); k=k+2){
       
        if(k+1 == A.size()){
            return A[k];
        }
        if(A[k] != A[k+1]){
            return A[k];
        }
    }
}
lastchance (6980)
@frek, in your last code (it's getting quite complex to remember which example you are referring to) both your methods have time complexity O(N log N). Unless you are doing a counting sort (not realistic here), both creating a set and sorting are going to have that complexity.
Duthomhas (13206)
This last one is a very simple variation of the first one.

I’m still not convinced @frek isn’t just stringing us along for answers by posting stuff he hasn’t done or thought about himself... I just thought the in-place rotate looked fun — It’s the only reason I’m here.

Is this for a competition site or something? Or homeworks your professor cribbed from one?

[edit] If you are actually doing and learning, good, good. Your presentation here looks suspiciously bad.
Last edited on
Pages: 12