Find Int That Appears Odd Number of Times

Approach 1

  1. Let curX be the first element of the list.

  2. Count how many times curX appear in the list.

    1. If the result is odd, return curX.

    2. If the result is even or zero.

    3. Let curX be the next element of the list.

  3. Repeat steps 2 to 4, getting the next element of the list each time (elem 3, elem 4, etc.).

  4. If reach the end of the list without getting an odd count, then return false.

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)))))))