Tasks Details
easy
1.
Distinct
Compute number of distinct values in an array.
Task Score
100%
Correctness
100%
Performance
100%
Write a function
int solution(vector<int> &A);
that, given an array A consisting of N integers, returns the number of distinct values in array A.
For example, given array A consisting of six elements such that:
A[0] = 2 A[1] = 1 A[2] = 1 A[3] = 2 A[4] = 3 A[5] = 1the function should return 3, because there are 3 distinct values appearing in array A, namely 1, 2 and 3.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..100,000];
- each element of array A is an integer within the range [−1,000,000..1,000,000].
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C++
Time spent on task 7 minutes
Notes
not defined yet
Task timeline
Code: 14:41:54 UTC,
java,
autosave
Code: 14:41:55 UTC,
cpp,
autosave
Code: 14:42:15 UTC,
cpp,
autosave
Code: 14:42:32 UTC,
cpp,
autosave
Code: 14:43:01 UTC,
cpp,
autosave
Code: 14:43:11 UTC,
cpp,
autosave
Code: 14:43:21 UTC,
cpp,
verify,
result: Failed
Analysis
Compile error
In file included from /opt/lang/gcc/include/c++/6.2.0/backward/hash_map:60:0,
from func.cpp:3:
/opt/lang/gcc/include/c++/6.2.0/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header which may be removed without further notice at a future date. Please use a non-deprecated interface with equivalent functionality instead. For a listing of replacement headers and interfaces, consult the file backward_warning.h. To disable this warning use -Wno-deprecated. [-Wcpp]
#warning \
^~~~~~~
func.cpp: In function 'int solution(std::vector<int>&)':
func.cpp:9:5: error: 'hash_map' was not declared in this scope
hash_map<int> h_map;
^~~~~~~~
func.cpp:9:5: note: suggested alternative:
In file included from func.cpp:3:0:
/opt/lang/gcc/include/c++/6.2.0/backward/hash_map:83:11: note: '__gnu_cxx::hash_map'
class hash_map
^~~~~~~~
func.cpp:9:14: error: expected primary-expression before 'int'
hash_map<int> h_map;
^~~
func.cpp:12:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
Code: 14:45:11 UTC,
cpp,
autosave
Code: 14:45:32 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <hash_set>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
using namespace stdext;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
hash_set<int> h_map;
}
Code: 14:45:43 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <hash_set>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
using namespace stdext;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
hash_set<int> h_set;
}
Code: 14:46:13 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <hash_set>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
using namespace stdext;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
hash_set<int> h_set;
for_each(A.begin(), A.end(), [&](auto& num){
})
}
Code: 14:46:31 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <hash_set>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
using namespace stdext;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
hash_set<int> h_set;
for_each(A.begin(), A.end(), [&](auto& num){
h_set.insert
});
}
Code: 14:46:42 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <hash_set>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
using namespace stdext;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
hash_set<int> h_set;
for_each(A.begin(), A.end(), [&](auto& num){
h_set.insert(num);
});
}
Code: 14:46:47 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
#include <algorithm>
#include <hash_set>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
using namespace stdext;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
hash_set<int> h_set;
for_each(A.begin(), A.end(), [&](auto& num){
h_set.insert(num);
});
return h_set.size();
}
Analysis
Compile error
In file included from /opt/lang/gcc/include/c++/6.2.0/backward/hash_set:60:0,
from func.cpp:3:
/opt/lang/gcc/include/c++/6.2.0/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header which may be removed without further notice at a future date. Please use a non-deprecated interface with equivalent functionality instead. For a listing of replacement headers and interfaces, consult the file backward_warning.h. To disable this warning use -Wno-deprecated. [-Wcpp]
#warning \
^~~~~~~
func.cpp:7:17: error: 'stdext' is not a namespace-name
using namespace stdext;
^~~~~~
func.cpp:7:23: error: expected namespace-name before ';' token
using namespace stdext;
^
func.cpp: In function 'int solution(std::vector<int>&)':
func.cpp:11:5: error: 'hash_set' was not declared in this scope
hash_set<int> h_set;
^~~~~~~~
func.cpp:11:5: note: suggested alternative:
In file included from func.cpp:3:0:
/opt/lang/gcc/include/c++/6.2.0/backward/hash_set:84:11: note: '__gnu_cxx::hash_set'
class hash_set
^~~~~~~~
func.cpp:11:14: error: expected primary-expression before 'int'
hash_set<int> h_set;
^~~
func.cpp: In lambda function:
func.cpp:14:8: error: 'h_set' was not declared in this scope
h_set.insert(num);
^~~~~
func.cpp: In function 'int solution(std::vector<int>&)':
func.cpp:17:12: error: 'h_set' was not declared in this scope
return h_set.size();
^~~~~
Code: 14:47:34 UTC,
cpp,
autosave
// you can use includes, for example:
#include <algorithm>
#include <hash_set>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
using namespace std
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
hash_set<int> h_set;
for_each(A.begin(), A.end(), [&](auto& num){
h_set.insert(num);
});
return h_set.size();
}
Code: 14:47:43 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
#include <algorithm>
#include <set>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
using namespace std
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
hash_set<int> h_set;
for_each(A.begin(), A.end(), [&](auto& num){
h_set.insert(num);
});
return h_set.size();
}
Analysis
Compile error
func.cpp:9:1: error: expected ';' before 'int'
int solution(vector<int> &A) {
^~~
func.cpp: In function 'int solution(std::vector<int>&)':
func.cpp:11:5: error: 'hash_set' was not declared in this scope
hash_set<int> h_set;
^~~~~~~~
func.cpp:11:14: error: expected primary-expression before 'int'
hash_set<int> h_set;
^~~
func.cpp: In lambda function:
func.cpp:14:8: error: 'h_set' was not declared in this scope
h_set.insert(num);
^~~~~
func.cpp: In function 'int solution(std::vector<int>&)':
func.cpp:17:12: error: 'h_set' was not declared in this scope
return h_set.size();
^~~~~
Code: 14:47:50 UTC,
cpp,
verify,
result: Failed
// you can use includes, for example:
#include <algorithm>
#include <set>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
using namespace std
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
set<int> h_set;
for_each(A.begin(), A.end(), [&](auto& num){
h_set.insert(num);
});
return h_set.size();
}
Analysis
Compile error
func.cpp:9:1: error: expected ';' before 'int'
int solution(vector<int> &A) {
^~~
Code: 14:48:14 UTC,
cpp,
verify,
result: Passed
// you can use includes, for example:
#include <algorithm>
#include <set>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
using namespace std;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
set<int> h_set;
for_each(A.begin(), A.end(), [&](auto& num){
h_set.insert(num);
});
return h_set.size();
}
Analysis
Code: 14:48:18 UTC,
cpp,
verify,
result: Passed
// you can use includes, for example:
#include <algorithm>
#include <set>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
using namespace std;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
set<int> h_set;
for_each(A.begin(), A.end(), [&](auto& num){
h_set.insert(num);
});
return h_set.size();
}
Analysis
Code: 14:48:21 UTC,
cpp,
final,
score:
100
// you can use includes, for example:
#include <algorithm>
#include <set>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
using namespace std;
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
set<int> h_set;
for_each(A.begin(), A.end(), [&](auto& num){
h_set.insert(num);
});
return h_set.size();
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N*log(N)) or O(N)
expand all
Correctness tests
1.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
1.
0.001 s
OK
1.
0.001 s
OK
1.
0.001 s
OK
1.
0.001 s
OK
1.
0.001 s
OK
1.
0.001 s
OK
1.
0.001 s
OK