LeetCode - Algorithms - 26. Remove Duplicates from Sorted Array

Java

The size of a Java array is fixed when you allocate it, and cannot be changed.

You’ve to provide a fixed size for that Array, You can neither EXPAND or SHRINK that array.

1

26.[圖解]Remove Duplicates from Sorted Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int removeDuplicates(int[] nums) {
    	if (nums.length<2) return nums.length;
    	int x=0,y=1;
    	while (y<nums.length) {
    		if (nums[x]==nums[y]) {
    			y+=1;
    		}
    		else {
    			x+=1;
    			nums[x]=nums[y];
    			y+=1;
    		}
    	}
        return x+1;        
    }
}

Submission Detail

  • 161 / 161 test cases passed.
  • Runtime: 6 ms
  • Memory Usage: 39.8 MB
  • Your runtime beats 97.51 % of java submissions.

2

5 lines Java solution

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int removeDuplicates(int[] nums) {
    	if (nums.length==0) return 0;
    	int j=0;
    	for(int i=0;i<nums.length;i++) {
    		if (nums[i]!=nums[j])
    			nums[++j]=nums[i];
    	}
    	return ++j;       
    }
}

Submission Detail

  • 161 / 161 test cases passed.
  • Runtime: 7 ms
  • Memory Usage: 42 MB
  • Your runtime beats 61.11 % of java submissions.

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    if (nums.length < 2) return nums.length;
    for (var i = 0; i < nums.length; i++) {
        while (nums[i] === nums[i-1]) 
            nums.splice(i, 1);
    }
    return nums.length;    
};

Submission Detail

  • 161 / 161 test cases passed.
  • Runtime: 84 ms, faster than 42.35% of JavaScript online submissions for Remove Duplicates from Sorted Array.
  • Memory Usage: 37.7 MB, less than 22.92% of JavaScript online submissions for Remove Duplicates from Sorted Array.

Resources

LeetCode - Algorithms - 13. Roman to Integer

Java

JAVA—————-Easy Version To Understand!!!!

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
class Solution {
    public int romanToInt(String s) {
    	if (s==null || s.isEmpty()) return -1;
    	Map<Character, Integer> map = new HashMap<Character, Integer>();
        map.put('I',1);
        map.put('V',5);
        map.put('X',10);
        map.put('L',50);
        map.put('C',100);
        map.put('D',500);
        map.put('M',1000);    	
    	char[] arr = s.toCharArray();
    	int len = arr.length;
    	int sum = map.get(arr[len-1]);
    	for(int i=0;i<len-1;i++) {
    		if (map.get(arr[i])>=map.get(arr[i+1])) {
    			sum += map.get(arr[i]);
    		}
    		else {
    			sum -= map.get(arr[i]);
    		}
    	}
        return sum;        
    }
}

Submission Detail

  • 3999 / 3999 test cases passed.
  • Runtime: 91 ms
  • Your runtime beats 20.92 % of java submissions.

LeetCode - Algorithms - 21. Merge Two Sorted Lists

I am confused with pointer and linked list since I tounched computer as freshman in university.

just verify solution of other guys.

Java

Iterative

© LeetCode – Merge Two Sorted Lists (Java)

The key to solve the problem is defining a fake head. Then compare the first elements from each list. Add the smaller one to the merged list. Finally, when one of them is empty, simply append it to the merged list, since it is already sorted.

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		ListNode head = new ListNode(0);
		ListNode p = head;

		ListNode p1 = l1;
		ListNode p2 = l2;
		while (p1 != null && p2 != null) {
			if (p1.val < p2.val) {
				p.next = p1;
				p1 = p1.next;
			} else {
				p.next = p2;
				p2 = p2.next;
			}
			p = p.next;
		}

		if (p1 != null) {
			p.next = p1;
		}

		if (p2 != null) {
			p.next = p2;
		}

		return head.next;        
    }
}

Submission Detail

  • 208 / 208 test cases passed.
  • Runtime: 1 ms, faster than 20.84% of Java online submissions for Merge Two Sorted Lists.
  • Memory Usage: 40.2 MB, less than 12.09% of Java online submissions for Merge Two Sorted Lists.

Recursive

Java, 1 ms, 4 lines codes, using recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    	if (l1==null) return l2;
    	if (l2==null) return l1;
    	if (l1.val<l2.val) {
    		l1.next = mergeTwoLists(l1.next,l2);
    		return l1;
    	}
    	else {
    		l2.next = mergeTwoLists(l1,l2.next);
    		return l2;
    	}        
    }
}

Submission Detail

  • 208 / 208 test cases passed.
  • Runtime: 13 ms
  • Your runtime beats 34.74 % of java submissions.

LeetCode - Algorithms - 393. UTF-8 Validation

Just verify code of others.

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean validUtf8(int[] data) {
    	int count=0;
    	for(int k : data) {
    		if (count==0) {
    			if ((k>>5)==0b110) count=1;
    			else if ((k>>4)==0b1110) count=2;
    			else if ((k>>3)==0b11110) count=3;
    			else if ((k>>7)==1) return false;
    		}
    		else {
    			if ((k>>6)!=0b10) return false;
    			count--;
    		}
    	}
    	return count==0;        
    }
}

binary (introduced in Java SE 7) 0b11110101 (0b followed by a binary number)

Submission Detail

  • 49 / 49 test cases passed.
  • Runtime: 6 ms
  • Your runtime beats 27.65 % of java submissions.

ref

LeetCode - Algorithms - 384. Shuffle an Array

It seemed that Spotify only let you click big green SHUFFLE PLAY button if you are not premium user.

Java

1 - Fisher–Yates shuffle

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
import java.util.Random;

class Solution {
	private int[] shuffleArr;
	private int[] originalArr;    

    public Solution(int[] nums) {
    	originalArr = nums.clone();
    	shuffleArr = nums.clone();       
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return originalArr;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
    	Random random = new Random();
    	int temp = 0;
    	int randomPosition = 0;
    	final int N = shuffleArr.length;
    	for(int i=shuffleArr.length-1;i>0;i--) {
    		randomPosition = random.nextInt(N);
    		temp = shuffleArr[i];
    		shuffleArr[i] = shuffleArr[randomPosition];
    		shuffleArr[randomPosition] = temp;
    	}
        return shuffleArr;
    }
}

Submission Detail

  • 10 / 10 test cases passed.
  • Runtime: 210 ms
  • Your runtime beats 38.29 % of java submissions.

2 the Knuth (or Fisher-Yates) shuffling algorithm

© Robert Sedgewick and Kevin Wayne

Proposition. [Fisher-Yates 1938] Knuth shuffling algorithm produces a uniformly random permutation of the input array in linear time.

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
class Solution {
    private int[] shuffleArr;
    private int[] originalArr;
    
    public Solution(int[] nums) {
        originalArr = nums.clone();
        shuffleArr = nums.clone();
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return originalArr;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        final int N = shuffleArr.length;
        int swap;
        for (int i = 0; i < N; i++) {
            int r = (int) (Math.random() * (i + 1));
            swap = shuffleArr[r];
            shuffleArr[r] = shuffleArr[i];
            shuffleArr[i] = swap;
        }
        return shuffleArr;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

Submission Detail

  • 10 / 10 test cases passed.
  • Runtime: 76 ms, faster than 76.75% of Java online submissions for Shuffle an Array.
  • Memory Usage: 47.2 MB, less than 6.24% of Java online submissions for Shuffle an Array.

3 - Collections.shuffle

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
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
	private Integer[] shuffleArr;
	private int[] originalArr;    

    public Solution(int[] nums) {
    	shuffleArr = new Integer[nums.length];
    	for(int i=0;i<nums.length;i++)
    		shuffleArr[i] = nums[i];
    	originalArr = nums.clone();       
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return originalArr;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
    	List<Integer> list = Arrays.asList(shuffleArr);
    	Collections.shuffle(list);
    	Integer[] a = new Integer[shuffleArr.length];
    	list.toArray(a);
    	int[] r = new int[a.length];
    	for(int i=0;i<a.length;i++)
    		r[i] = a[i];
        return r;        
    }
}

Submission Detail

  • 10 / 10 test cases passed.
  • Runtime: 141 ms
  • Your runtime beats 96.48 % of java submissions.

ref

LeetCode - Algorithms - 706. Design HashMap

In Java collections framework, HashMap is the class I used most. Hash function is a hard problem.

Java

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
class MyHashMap {
    static final int N = 1000000;
	private int[] arr;

    /** Initialize your data structure here. */
    public MyHashMap() {
        arr = new int[N];
        Arrays.fill(arr, -1);        
    }

    /** value will always be non-negative. */
    public void put(int key, int value) {
        arr[key]=value;
    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        return arr[key];
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        arr[key]=-1;
    }
}

Submission Detail

  • 33 / 33 test cases passed.
  • Runtime: 150 ms
  • Your runtime beats 13.66 % of java submissions.

LeetCode - Algorithms - 53. Maximum Subarray

Tagged as easy, I feel it is not easy to solve. dynamic programming class problem. The solution is others, I only verify it.

Java

1 Kadane’s algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxSubArray(int[] nums) {
    	int max = Integer.MIN_VALUE;
    	int count = 0;
    	for(int i=0;i<nums.length;i++) {
    		count += nums[i];
    		if (count>max)
    			max = count;
    		if (count<0)
    			count = 0;
    	}
    	return max;        
    }
}

Submission Detail

  • 202 / 202 test cases passed.
  • Runtime: 10 ms
  • Your runtime beats 40.59 % of java submissions.

2 DP

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxSubArray(int[] nums) {
        int newSum = nums[0];
        int max = nums[0];
        for(int i=1;i<nums.length;i++) {
        	newSum = Math.max(newSum+nums[i], nums[i]);
        	max = Math.max(newSum, max);
        }
        return max;        
    }
}

Submission Detail

  • 202 / 202 test cases passed.
  • Runtime: 7 ms
  • Your runtime beats 89.29 % of java submissions.

ref

LeetCode - Algorithms - 69. Sqrt(x)

Java

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int mySqrt(int x) {
		if (x < 0)
			return 0;
		else if (x < 2)
			return x;
		else {
			long smallCandidate = mySqrt(x >> 2) << 1;
			long largeCandidate = smallCandidate + 1;
			if (largeCandidate*largeCandidate > x)
				return new Long(smallCandidate).intValue();
			else
				return new Long(largeCandidate).intValue();
		}       
    }
}

Submission Detail

  • 1017 / 1017 test cases passed.
  • Runtime: 36 ms
  • Your runtime beats 17.73 % of java submissions.

2

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int mySqrt(int x) {
		if (x==0 || x==1) return x;
		long i=1, result=1;
		while(result<=x) {
			i++;
			result = i*i;
		}
		return new Long(i-1).intValue();       
    }
}

Submission Detail

  • 1017 / 1017 test cases passed.
  • Runtime: 33 ms
  • Your runtime beats 24.03 % of java submissions.

3 O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int mySqrt(int x) {
		if (x == 0 || x == 1)
			return x;

		long start = 1, end = x, ans = 0;
		while (start <= end) {
			long mid = (start + end) / 2;

			if (mid * mid == x)
				return new Long(mid).intValue();

			if (mid * mid < x) {
				start = mid + 1;
				ans = mid;
			} else
				end = mid - 1;
		}
		return new Long(ans).intValue();       
    }
}

Submission Detail

  • 1017 / 1017 test cases passed.
  • Runtime: 16 ms
  • Your runtime beats 95.09 % of java submissions.

ref

LeetCode - Algorithms - 217. Contains Duplicate

Tag easy as it is. This problem is like 387. First Unique Character in a String.

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean containsDuplicate(int[] nums) {
    	boolean r = false;
    	Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    	for(int i=0;i<nums.length;i++) {
    		if (map.containsKey(nums[i])) {
    			int val = map.get(nums[i]);
    			map.put(nums[i], val+1);
    		}
    		else {
    			map.put(nums[i], 1);
    		}
    	}
    	Iterator<Integer> itr = map.values().iterator();
    	while(itr.hasNext()) {
    		if (itr.next().intValue()>1) {
    			r = true;
    			break;
    		}
    	}
    	return r;        
    }
}

Submission Detail

  • 18 / 18 test cases passed.
  • Runtime: 13 ms
  • Your runtime beats 48.76 % of java submissions.

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
	var r = false;
	var count = {};
	for(var i=0;i<nums.length;i++) {
		if (typeof count[nums[i]]!="undefined" && count[nums[i]]!=null) {
			count[nums[i]]++;
		}
		else {
			count[nums[i]]=1;
		}
	}
	for(var i in count) {
		if (count[i]>1) {
			r = true;
			break;
		}
	}
	return r;    
};

Submission Detail

  • 18 / 18 test cases passed.
  • Runtime: 92 ms
  • Your runtime beats 35.80 % of javascript submissions.

AKS test for primes

Manindra Agrawal & Neeraj Kayal & Nitin Saxena present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite.

The AKS algorithm for testing whether a number is prime is a polynomial-time algorithm based on an elementary theorem about Pascal triangles.

Rust

1

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
use std::iter::repeat;
 
fn aks_coefficients(k: usize) -> Vec<i64> {
    let mut coefficients = repeat(0i64).take(k + 1).collect::<Vec<_>>();
    coefficients[0] = 1;
    for i in 1..(k + 1) {
        coefficients[i] = -(1..i).fold(coefficients[0], |prev, j|{
            let old = coefficients[j];
            coefficients[j] = old - prev;
            old
        });
    }
    coefficients
}
 
fn is_prime(p: usize) -> bool {
    if p < 2 {
        false
    } else {
        let c = aks_coefficients(p);
        (1 .. (c.len() - 1) / 2 + 1).all(|i| (c[i] % (p as i64)) == 0)
    }
}
 
fn main() {
    for i in 0..8 {
        println!("{}: {:?}", i, aks_coefficients(i));
    }
    for i in (1..51).filter(|&i| is_prime(i)) {
        print!("{} ", i);
    }
}

2

An alternative version which computes the coefficients in a more functional but less efficient way. 

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
fn aks_coefficients(k: usize) -> Vec<i64> {
	if k == 0 {
		vec![1i64]
	} else {
		let zero = Some(0i64);
		(1..k).fold(vec![1i64, -1], |r, _| {
			let a = r.iter().chain(zero.iter());
			let b = zero.iter().chain(r.iter());
			a.zip(b).map(|(x, &y)| x-y).collect()
		})
	}
}
 
fn is_prime(p: usize) -> bool {
    if p < 2 {
        false
    } else {
        let c = aks_coefficients(p);
        (1 .. (c.len() - 1) / 2 + 1).all(|i| (c[i] % (p as i64)) == 0)
    }
}
 
fn main() {
    for i in 0..8 {
        println!("{}: {:?}", i, aks_coefficients(i));
    }
    for i in (1..51).filter(|&i| is_prime(i)) {
        print!("{} ", i);
    }
}

Java

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
public class AksTest {
	
    private static final long[] c = new long[64];
    
    public static void main(String[] args) {
        for (int n = 0; n < 10; n++) {
            coeff(n);
            show(n);
        }
 
        System.out.print("Primes:");
        for (int n = 1; n < c.length; n++)
            if (isPrime(n))
                System.out.printf(" %d", n);
 
        System.out.println();
    }    
 
    static void coeff(int n) {
        c[0] = 1;
        for (int i = 0; i < n; c[0] = -c[0], i++) {
            c[1 + i] = 1;
            for (int j = i; j > 0; j--)
                c[j] = c[j - 1] - c[j];
        }
    }
 
    static boolean isPrime(int n) {
        coeff(n);
        c[0]++;
        c[n]--;
 
        int i = n;
        while (i-- != 0 && c[i] % n == 0)
            continue;
        return i < 0;
    }
 
    static void show(int n) {
        System.out.print("(x-1)^" + n + " =");
        for (int i = n; i >= 0; i--) {
            System.out.print(" + " + c[i] + "x^" + i);
        }
        System.out.println();
    }
}

JavaScript

Translation of: C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function coef(n) {
 	for (var c=[1], i=0; i<n; c[0]=-c[0], i+=1) {
		c[i+1]=1; for (var j=i; j; j-=1) c[j] = c[j-1]-c[j]		
	}
	return c
}
 
function show(cs)	{
	var s='', n=cs.length-1
	do s += (cs[n]>0 ? ' +' : ' ') + cs[n] + (n==0 ? '' : n==1 ? 'x' :'x<sup>'+n+'</sup>'); while (n--)
	return s
}
 
function isPrime(n) {
	var cs=coef(n), i=n-1; while (i-- && cs[i]%n == 0);
	return i < 1
}
 
for (var n=0; n<=7; n++) document.write('(x-1)<sup>',n,'</sup> = ', show(coef(n)), '<br>')
 
document.write('<br>Primes: ');
for (var n=2; n<=50; n++) if (isPrime(n)) document.write(' ', n)

Translation of: CoffeeScript

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
76
77
78
79
var i, p, pascal, primerow, primes, show, _i;

pascal = function() {
  var a;
  a = [];
  return function() {
    var b, i;
    if (a.length === 0) {
      return a = [1];
    } else {
      b = (function() {
        var _i, _ref, _results;
        _results = [];
        for (i = _i = 0, _ref = a.length - 1; 0 <= _ref ? _i < _ref : _i > _ref; i = 0 <= _ref ? ++_i : --_i) {
          _results.push(a[i] + a[i + 1]);
        }
        return _results;
      })();
      return a = [1].concat(b).concat([1]);
    }
  };
};
 
show = function(a) {
  var degree, i, sgn, show_x, str, _i, _ref;
  show_x = function(e) {
    switch (e) {
      case 0:
        return "";
      case 1:
        return "x";
      default:
        return "x^" + e;
    }
  };
  degree = a.length - 1;
  str = "(x - 1)^" + degree + " =";
  sgn = 1;
  for (i = _i = 0, _ref = a.length; 0 <= _ref ? _i < _ref : _i > _ref; i = 0 <= _ref ? ++_i : --_i) {
    str += ' ' + (sgn > 0 ? "+" : "-") + ' ' + a[i] + show_x(degree - i);
    sgn = -sgn;
  }
  return str;
};
 
primerow = function(row) {
  var degree;
  degree = row.length - 1;
  return row.slice(1, degree).every(function(x) {
    return x % degree === 0;
  });
};
 
p = pascal();
 
for (i = _i = 0; _i <= 7; i = ++_i) {
  console.log(show(p()));
}
 
p = pascal();
 
p();
 
p();
 
primes = (function() {
  var _j, _results;
  _results = [];
  for (i = _j = 1; _j <= 49; i = ++_j) {
    if (primerow(p())) {
      _results.push(i + 1);
    }
  }
  return _results;
})();
 
console.log("");
 
console.log("The primes upto 50 are: " + primes);

Reviewed (ES6)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function pascal(n) {
	var cs = []; if (n) while (n--) coef(); return coef
	function coef() {
		if (cs.length === 0) return cs = [1];
		for (var t=[1,1], i=cs.length-1; i; i-=1) t.splice( 1, 0, cs[i-1]+cs[i] ); return cs = t
	}
}

function show(cs) {
	for (var s='', sgn=true, i=0, deg=cs.length-1; i<=deg; sgn=!sgn, i+=1) {
		s += ' ' + (sgn ? '+' : '-') + cs[i] + (e => e==0 ? '' : e==1 ? 'x' : 'x<sup>' + e + '</sup>')(deg-i)
	}
	return '(x-1)<sup>' + deg + '</sup> =' + s;
}

function isPrime(cs) {
	var deg=cs.length-1; return cs.slice(1, deg).every( function(c) { return c % deg === 0 } )
}

var coef=pascal(); for (var i=0; i<=7; i+=1) document.write(show(coef()), '<br>')

document.write('<br>Primes: ');
for (var coef=pascal(2), n=2; n<=50; n+=1) if (isPrime(coef())) document.write(' ', n)

ref