JAVA: I needed help creating a method that will generate a sparse table, without
ID: 3842489 • Letter: J
Question
JAVA:
I needed help creating a method that will generate a sparse table, without using for or while loops or creating any additional methods
I'll post the code that's given and ask the question at the end in bold:
public static long random(long n){
if (n == 0){
return 1;
}
return (random(n/4))+(random(3*n/4));
public static void exampleTable(int a, int z)
long exampleOne = random(a);
System.out.println(a+" "+exampleOne);
if (start != end){
exampleTable(a+1, z);
}
I'll then have a tester that will input values for example from 13 to 20.
Right now it would print out:
13 15
14 15
15 18
16 21
17 21
18 21
19 21
20 24
WHAT I NEED THE OUTPUT TO BE IS:
13 15
15 18
16 21
20 24
I need to know how to skip over duplicate values and get the output I just listed. Again, I can't use any loops, or whiles, or create any additional methods.
Explanation / Answer
public class RmqSparseTable {
int[] logTable;
int[][] rmq;
int[] a;
public RmqSparseTable(int[] a) {
this.a = a;
int n = a.length;
logTable = new int[n + 1];
for (int i = 2; i <= n; i++)
logTable[i] = logTable[i >> 1] + 1;
rmq = new int[logTable[n] + 1][n];
for (int i = 0; i < n; ++i)
rmq[0][i] = i;
for (int k = 1; (1 << k) < n; ++k) {
for (int i = 0; i + (1 << k) <= n; i++) {
int x = rmq[k - 1][i];
int y = rmq[k - 1][i + (1 << k - 1)];
rmq[k][i] = a[x] <= a[y] ? x : y;
}
}
}
public int minPos(int i, int j) {
int k = logTable[j - i];
int x = rmq[k][i];
int y = rmq[k][j - (1 << k) + 1];
return a[x] <= a[y] ? x : y;
}
public static void main(String[] args) {
int[] a = { 1, 5, -2, 3 };
RmqSparseTable st = new RmqSparseTable(a);
System.out.println(2 == st.minPos(0, 3));
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.