Tasks Details
easy
1.
Distinct
Compute number of distinct values in an array.
Task Score
100%
Correctness
100%
Performance
100%
Write a function
function solution(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 JavaScript
Time spent on task 7 minutes
Notes
not defined yet
Task timeline
Code: 00:07:22 UTC,
java,
autosave
function solution(A) {
var M = []
for (var i = 0; i < A.length; i++) {
var idx = binarySearch(M, A[i]);
if(M[idx] != A[i]){
M.splice(idx, 0, A[i])
}
}
//console.log(M)
return M.length
}
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:07:23 UTC,
java,
autosave
function solution(A) {
var M = []
for (var i = 0; i < A.length; i++) {
var idx = binarySearch(M, A[i]);
if(M[idx] != A[i]){
M.splice(idx, 0, A[i])
}
}
//console.log(M)
return M.length
}
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:07:35 UTC,
js,
autosave
function solution(A) {
var M = 0
for (var i = 0; i < A.length; i++) {
var idx = binarySearch(M, A[i]);
if(M[idx] != A[i]){
M.splice(idx, 0, A[i])
}
}
//console.log(M)
return M.length
}
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:07:41 UTC,
js,
verify,
result: Failed
function solution(A) {
var M = 0
for (var i = 0; i < A.length; i++) {
var idx = binarySearch(M, A[i]);
if(M[idx] != A[i]){
M++
}
}
//console.log(M)
return M
}
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Analysis
expand all
Example tests
1.
0.060 s
WRONG ANSWER,
got 6 expected 3
Code: 00:08:25 UTC,
js,
autosave
function solution(A) {
var M = 0
for (var i = 0; i < A.length; i++) {
var idx = binarySearch(M, A[i]);
if(M[idx] != A[i]){
M.splice(idx, 0, A[i])
}
}
//console.log(M)
return M.length
}
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:08:35 UTC,
js,
autosave
function solution(A) {
var M = []
for (var i = 0; i < A.length; i++) {
var idx = binarySearch(M, A[i]);
if(M[idx] != A[i]){
M.splice(idx, 0, A[i])
}
}
//console.log(M)
return M.length
}
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:09:19 UTC,
js,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455
function solution(A) {
var M = []
for (var i = 0; i < A.length; i++) {
var idx = binarySearch(M, A[i]);
if(M[idx] != A[i]){
M.splice(idx, 0, A[i])
}
}
//console.log(M)
return M.length
}
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// 向鏈結串列尾部添加元素
add(data) {
const newNode = new Node(data);
if (!this.head) {
this.head = newNode;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:09:51 UTC,
js,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788
function solution(A) {
var M = []
for (var i = 0; i < A.length; i++) {
var idx = binarySearch(M, A[i]);
if(M[idx] != A[i]){
M.splice(idx, 0, A[i])
}
}
//console.log(M)
return M.length
}
class DoublyNode {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
// 在任意位置插入元素
insertAt(index, data) {
if (index < 0 || index > this.size) {
console.log("請輸入有效的索引");
return false;
}
const newNode = new DoublyNode(data);
let current = this.head;
let previous;
if (index === 0) {
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
} else if (index === this.size) {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
} else {
for (let i = 0; i < index; i++) {
previous = current;
current = current.next;
}
newNode.prev = previous;
newNode.next = current;
previous.next = newNode;
current.prev = newNode;
}
this.size++;
}
}
// 使用範例
const doublyLinkedList = new DoublyLinkedList();
doublyLinkedList.insertAt(0, 1);
doublyLinkedList.insertAt(1, 2);
doublyLinkedList.insertAt(2, 4);
doublyLinkedList.insertAt(2, 3); // 在索引 2 處插入元素 3
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:10:01 UTC,
js,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788
function solution(A) {
var M = []
for (var i = 0; i < A.length; i++) {
var idx = binarySearch(M, A[i]);
if (M[idx] != A[i]) {
M.splice(idx, 0, A[i])
}
}
//console.log(M)
return M.length
}
class DoublyNode {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
// 在任意位置插入元素
insertAt(index, data) {
if (index < 0 || index > this.size) {
console.log("請輸入有效的索引");
return false;
}
const newNode = new DoublyNode(data);
let current = this.head;
let previous;
if (index === 0) {
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
} else if (index === this.size) {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
} else {
for (let i = 0; i < index; i++) {
previous = current;
current = current.next;
}
newNode.prev = previous;
newNode.next = current;
previous.next = newNode;
current.prev = newNode;
}
this.size++;
}
}
// 使用範例
const doublyLinkedList = new DoublyLinkedList();
doublyLinkedList.insertAt(0, 1);
doublyLinkedList.insertAt(1, 2);
doublyLinkedList.insertAt(2, 4);
doublyLinkedList.insertAt(2, 3); // 在索引 2 處插入元素 3
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:10:17 UTC,
js,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
function solution(A) {
var M = []
for (var i = 0; i < A.length; i++) {
var idx = binarySearch(M, A[i]);
if (M[idx] != A[i]) {
M.splice(idx, 0, A[i])
}
}
//console.log(M)
return M.length
}
class DoublyNode {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
// 在任意位置插入元素
insertAt(index, data) {
if (index < 0 || index > this.size) {
return false;
}
const newNode = new DoublyNode(data);
let current = this.head;
let previous;
if (index === 0) {
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
} else if (index === this.size) {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
} else {
for (let i = 0; i < index; i++) {
previous = current;
current = current.next;
}
newNode.prev = previous;
newNode.next = current;
previous.next = newNode;
current.prev = newNode;
}
this.size++;
}
}
// 使用範例
const doublyLinkedList = new DoublyLinkedList();
doublyLinkedList.insertAt(0, 1);
doublyLinkedList.insertAt(1, 2);
doublyLinkedList.insertAt(2, 4);
doublyLinkedList.insertAt(2, 3); // 在索引 2 處插入元素 3
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:10:36 UTC,
js,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
function solution(A) {
var M = []
for (var i = 0; i < A.length; i++) {
var idx = binarySearch(M, A[i]);
if (M[idx] != A[i]) {
M.splice(idx, 0, A[i])
}
}
//console.log(M)
return M.length
}
class DoublyNode {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
// 在任意位置插入元素
insertAt(index, data) {
if (index < 0 || index > this.size) {
return false;
}
const newNode = new DoublyNode(data);
let current = this.head;
let previous;
if (index === 0) {
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
} else if (index === this.size) {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
} else {
for (let i = 0; i < index; i++) {
previous = current;
current = current.next;
}
newNode.prev = previous;
newNode.next = current;
previous.next = newNode;
current.prev = newNode;
}
this.size++;
}
}
// 使用範例
doublyLinkedList.insertAt(0, 1);
doublyLinkedList.insertAt(1, 2);
doublyLinkedList.insertAt(2, 4);
doublyLinkedList.insertAt(2, 3); // 在索引 2 處插入元素 3
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:10:47 UTC,
js,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
function solution(A) {
var M = const doublyLinkedList = new DoublyLinkedList();
for (var i = 0; i < A.length; i++) {
var idx = binarySearch(M, A[i]);
if (M[idx] != A[i]) {
M.splice(idx, 0, A[i])
}
}
//console.log(M)
return M.length
}
class DoublyNode {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
// 在任意位置插入元素
insertAt(index, data) {
if (index < 0 || index > this.size) {
return false;
}
const newNode = new DoublyNode(data);
let current = this.head;
let previous;
if (index === 0) {
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
} else if (index === this.size) {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
} else {
for (let i = 0; i < index; i++) {
previous = current;
current = current.next;
}
newNode.prev = previous;
newNode.next = current;
previous.next = newNode;
current.prev = newNode;
}
this.size++;
}
}
// 使用範例
doublyLinkedList.insertAt(0, 1);
doublyLinkedList.insertAt(1, 2);
doublyLinkedList.insertAt(2, 4);
doublyLinkedList.insertAt(2, 3); // 在索引 2 處插入元素 3
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:10:57 UTC,
js,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
function solution(A) {
const doublyLinkedList = new DoublyLinkedList();
for (var i = 0; i < A.length; i++) {
var idx = binarySearch(M, A[i]);
if (M[idx] != A[i]) {
M.splice(idx, 0, A[i])
}
}
//console.log(M)
return M.length
}
class DoublyNode {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
// 在任意位置插入元素
insertAt(index, data) {
if (index < 0 || index > this.size) {
return false;
}
const newNode = new DoublyNode(data);
let current = this.head;
let previous;
if (index === 0) {
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
} else if (index === this.size) {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
} else {
for (let i = 0; i < index; i++) {
previous = current;
current = current.next;
}
newNode.prev = previous;
newNode.next = current;
previous.next = newNode;
current.prev = newNode;
}
this.size++;
}
}
// 使用範例
doublyLinkedList.insertAt(0, 1);
doublyLinkedList.insertAt(1, 2);
doublyLinkedList.insertAt(2, 4);
doublyLinkedList.insertAt(2, 3); // 在索引 2 處插入元素 3
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:12:03 UTC,
js,
autosave
function solution(A) {
const doublyLinkedList = new DoublyLinkedList();
for (var i = 0; i < A.length; i++) {
var idx = binarySearch(M, A[i]);
if (M[idx] != A[i]) {
M.splice(idx, 0, A[i])
}
}
//console.log(M)
return M.length
}
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:12:18 UTC,
js,
autosave
function solution(A) {
var M
for (var i = 0; i < A.length; i++) {
var idx = binarySearch(M, A[i]);
if (M[idx] != A[i]) {
M.splice(idx, 0, A[i])
}
}
//console.log(M)
return M.length
}
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:12:28 UTC,
js,
autosave
function solution(A) {
var M = {}
for (var i = 0; i < A.length; i++) {
var idx = binarySearch(M, A[i]);
if (M[idx] != A[i]) {
M.splice(idx, 0, A[i])
}
}
//console.log(M)
return M.length
}
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:12:43 UTC,
js,
autosave
function solution(A) {
var M = {}
for (var i = 0; i < A.length; i++) {
}
//console.log(M)
return M.length
}
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:12:58 UTC,
js,
autosave
function solution(A) {
var M = {}
for (var i = 0; i < A.length; i++) {
M[A[i]]
}
//console.log(M)
return M.length
}
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:13:11 UTC,
js,
autosave
function solution(A) {
var M = {}
for (var i = 0; i < A.length; i++) {
M[A[i]] = true;
}
//console.log(M)
return M.length
}
//在一個已排序的陣列裡，取得newValue應插入的index
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left
}
Code: 00:13:57 UTC,
js,
verify,
result: Passed
Analysis
expand all
Example tests
1.
0.056 s
OK
stdout:
[ '1', '2', '3' ]
Code: 00:14:07 UTC,
js,
verify,
result: Passed
Analysis
Code: 00:14:12 UTC,
js,
verify,
result: Passed
Analysis
Code: 00:14:15 UTC,
js,
final,
score:
100
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N*log(N)) or O(N)
expand all
Correctness tests
1.
0.056 s
OK
1.
0.056 s
OK
2.
0.056 s
OK
1.
0.056 s
OK
1.
0.056 s
OK
1.
0.056 s
OK
1.
0.056 s
OK
1.
0.056 s
OK
1.
0.056 s
OK
1.
0.056 s
OK