Find Int That Appears Odd Number of Times¶
Approach 1 (search and count)¶
Let curX be the first element of the list.
Count how many times curX appear in the list.
If the result is odd, return curX.
If the result is even or zero.
Let curX be the next element of the list.
Repeat steps 2 to 4, getting the next element of the list each time (elem 3, elem 4, etc.).
If reach the end of the list without getting an odd count, then return false.
Approach 2 Bitwise XOR¶
Note
This approach only works, and works precisely because we are told there is always one — and always a single one — integer that appears an odd number of times. They state that:
“There will always be only one integer that appears an odd number of times.”
It is implied by that sentence and by the example test cases that there is never more than one integer that appears an odd number of times.
XORing \(x\) to itself an even number of times always yields \(0\).
1 ^ 1 = 0
1 ^ 1 ^ 1 ^ 1 = 0
XORing \(x\) to \(0\) yields \(x\).
1 ^ 0 = 1
5 ^ 0 = 5
If we XOR \(x\) an even number of times, the result is always \(0\). It means an even number of \(x\)’s cancel themselves.
For this challenge, since it is ASSUMED that there will be only one number that appears an even number of times (and there will always be one), we can use this bitwise XOR technique to obtain the answer.
1 ^ 1 ^ 3 = 3
1 ^ 2 ^ 1 ^ 2 ^ 3 = 3
The XOR operator has the associative and commutative properties. Thus, the order of the numbers in the array doesn’t matter for this case.
TypeScript¶
The original function in Codewars has a return type of simply number. I changed this to undefined | number to satisfy find even though the exercise says we can assume there will always be single number that appears an odd number of times.
Unit Tests¶
The unit tests should work for all approaches and solutions. Changing the implementation should not produce different results.
import { assertEquals } from '/deps.ts'
import { findN } from './find-n-v3.ts';
Deno.test('findN()', async (t) => {
await t.step('should work for array of single number', () => {
assertEquals(findN([0]), 0);
assertEquals(findN([7]), 7);
assertEquals(findN([-3]), -3);
});
await t.step('should work for array of three numbers', () => {
assertEquals(findN([0, 0, 0]), 0);
assertEquals(findN([7, 7, 7]), 7);
assertEquals(findN([-3, -3, -3]), -3);
});
await t.step('should work for array of other combinations', () => {
assertEquals(findN([0, 0, 2, 2, 0]), 0);
assertEquals(findN([7, 4, 7, 4, 4, 4, 7]), 7);
assertEquals(findN([-3, -7, -3, 7, -7, 7, -3]), -3);
});
});
Solution 1 (single function, approach 1)¶
Using approach 1, one single function that takes care of the entire logic. Not bad.
/**
* Returns the element that appears an odd number of times in `nums`.
*/
function findN(nums: number[]): undefined | number {
return nums.find(function hasOddOccurrences(x) {
return nums.filter(y => y === x).length % 2 !== 0;
});
}
export { findN };
Solution 2 (helper functions, approach 1)¶
Also using approach
1, we have the main
findN function which in turn makes use of specialized helper
functions. Looks overkill for this case but the helper functions could
be useful and used in other contexts as well, though. Therefore it is
worth the example.
/**
* Counts the number of occurrences of `x` in `xs`.
*/
function countX(x: number, xs: number[]): number {
return xs.filter(val => val === x).length;
}
/**
* Checks whether `x` appears an odd number of times in `xs`.
*/
function hasOddOccurrences(xs: number[]): (x: number) => boolean {
return function count(x: number): boolean {
return countX(x, xs) % 2 !== 0;
};
}
/**
* Returns the element that appears an odd number of times in `nums`.
*/
function findN(nums: number[]): undefined | number {
return nums.find(hasOddOccurrences(nums));
}
export { findN };
Solution 3 (bitwise XOR)¶
The clever solution with approach 2 using bitwise XOR! I did not come up with this solution myself, but instead saw it from other people’s solution. What I did was to write an explanation on how it works.
/**
* Returns the element that appears an odd number of times in `nums`.
*/
function findN(nums: number[]): number {
return nums.reduce((acc, n) => acc ^ n);
}
export { findN };
Scheme¶
The Test Suit¶
(import test)
;(load "find-n-v1.scm")
;(load "find-n-v2.scm")
(load "find-n-v3.scm")
(test-group
"find-n"
(test-group
"when input is an empty list"
(test "should find nothing"
#f
(find-n '())))
(test-group
"when input contains a single integer"
(test "should return that number"
7
(find-n '(7)))))
v1 single function¶
(import (only srfi-1 find filter))
;;
;; `Result` is one of:
;; • `#f`
;; • `Int`
;;
;;
;; Finds the integer that appears an odd number of times.
;;
;; @sig ListOf<Int> -> Result
;;
(define (find-n xs)
(find
(lambda (x)
(odd?
(length
(filter
(lambda (i)(= x i))
xs)))) xs))
v2 smaller, composable functions¶
Unit Tests for the Helper Functions¶
(import test)
(load "find-n-v2.scm")
(test-group
"eqx?"
(test-group
"should assert that two numbers are equal"
(test #t ((eqx? 1) 1))
(test #t ((eqx? 42) (+ 41 1))))
(test-group
"should that two numbers are different"
(test #f ((eqx? 1) -1))
(test #f ((eqx? 0) (- 0 1)))))
(test-group
"oddx?"
(test-group
"should return #t when input list contains odd number of x"
(test #t (oddx? 42 '(42)))
(test #t (oddx? 42 '(0 -42 42 1 42 -7 42))))
(test-group
"should return #f when input list contains even number of x"
(test #f (oddx? 42 '()))
(test #f (oddx? 42 '(-42)))
(test #f (oddx? 42 '(0 -42 42 1 -7 42)))))
Implementation using the composed functions¶
(import (only srfi-1 find filter))
;;
;; `Result` is one of:
;; • `#f`
;; • `Int`
;;
;;
;; Checks whether `x` equals `y`
;;
;; @curry
;;
;; @sig Int -> Int -> Bool
;;
;; @example
;; ((eqx? 1) 1)
;; ;; → #t
;;
;; @example
;; ((eqx? 1) -1)
;; ;; → #f
;;
;; @example
;; (define one? (eqx? 1))
;; (one? 1)
;; ;; → #t
;; (one? -1)
;; ;; → #f
;;
;(define ((eqx? x) y) (= x y))
(define (eqx? x)
(lambda (y)
(= x y)))
;;
;; Checks whether there is an odd number of `x` in `xs`.
;;
;; Int ListOf<Int> -> ListOf<Int>
;;
(define (oddx? x xs)
(odd? (length (filter (eqx? x) xs))))
;;
;; Finds the int that appears an odd number of times.
;;
;; ListOf<Int> -> Result
;;
(define (find-n xs)
(find (lambda (curX)
(oddx? curX xs)) xs))
In this case, we have a curried eqx? function that we partially
apply inside oddx? to help filter out and then count the number of
times the current x appear in the list.
v3 car cdr¶
This implementation is a courtesy of Mario Domenech Goulart. It
does not use find and filter and instead makes use of car,
cdr and null?. It does not need any help of external libraries
or SRFIs. It is probably the most idiomatic example in terms of
techniques used, like the loop pattern, for instance.
Unit Tests for the Helper Functions¶
(import test)
(load "find-n-v3.scm")
(test-group
"count-occurrences"
(test 0 (count-occurrences 7 '()))
(test 1 (count-occurrences 7 '(7)))
(test 2 (count-occurrences 7 '(7 -7 7 1)))
(test 5 (count-occurrences 7 '(7 1 7 2 7 7 3 7))))
Implementation using car, cdr and null?¶
;;
;; `Result` is one of:
;; • `#f`
;; • `Int`
;;
(define (count-occurrences x xs)
(let loop ((lst xs))
(if (null? lst)
0
(+ (if (= (car lst) x) 1 0)
(loop (cdr lst))))))
;;
;; Finds the int that appears an odd number of times.
;;
;; @sig ListOf<Int> -> Result
;;
(define (find-n lst)
(let loop ((nums lst))
(if (null? lst)
#f
(let ((cur-num (car nums)))
(if (odd? (count-occurrences cur-num lst))
cur-num
(loop (cdr nums)))))))