//@Description A read-only array with N elements contains the values {1,...,N-1}. This Sketch finds the duplicate entry using only constant extra space. int W = 17; pragma options "--bnd-inline-amnt 5 --bnd-inbits 3 "; bit dup(int[W] in) { int[W] tab = 0; int count = 0; for(int i = 0;i<W; i++) tab[in[i]] = tab[in[i]] + 1; for(int i = 0;i<W; i++) if(tab[i] > 1) count = count + 1; if(count ≥ 1) return 1; return 0; } generator int f(int[W] in, int n) { return in[n]; } generator int fstar(int[W] in, int n, int k) { for(int i = 1;i≤k; i++) n = f(in, n); return n; } generator int expr(int[W] in, int n, int flag) { if(flag == 1) return fstar(in, n, ??); else return fstar(in, n, ??); } bit dupSketched(int[W] in) implements dup{ int a,b; int count1 = ??; int count2 = ??; a = expr(in, W-1, 1); b = expr(in, W-1, 2); for(int i = 0; a != b; i++) { a = expr(in, a, 1); b = expr(in, b, 2); } //Computing length of tail a = W - ??; for(int i = 0; a != b; i++) { count2 = count2 + 1; a = f(in, a); b = f(in, b); } //Counting the length of cycle a = expr(in, a, 1); for(int i = 0; a != b; i++) { a = f(in, a); count1 = count1 + 1; } int count3 = ??; for(int i = 0;i<W; i++) if(in[i] == b) count3++; if(count1 + count2 + count3 ≥ W + ??) return 0; return 1; }