Finding the output of sequence (a + 2^(i*b))

I just started programming and have taken too much time to code the solution for this problem:

In this problem you will test your knowledge of Java loops. Given three integers, $a$, $b$, and $n$, output the following series:

$$a + 2^{0}b, a + 2^{0}b + 2^{1}b, \ldots \ldots, a + 2^{0}b + 2^{1}b + \ldots + 2^{n-1}b$$

Input Format

The first line will contain the number of testcases $t$. Each of the next $t$ lines will have three integers, $a$, $b$, and $n$.

Constraints:

• $0 \le t \le 500$
• $0 \le a, b \le 50$
• $1 \le n \le 15$

Output

Print the answer to each test case in separate lines.

I just want to know whether this code can be further optimized in Java.

import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) {
int r=0,c=1;
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
int a=sc.nextInt();
int b=sc.nextInt();
int n=sc.nextInt();
r=a;
for(int j=0;j<n;j++){
if(j==0)
c=1;
else
c=c*2;
r= r +c*b;
System.out.print(r +" " );
}
System.out.println( );
}
}
}

• Have you verified your code? I'm not convinced that r= r + c*b is correct, as you will be adding a too many times. Jul 12, 2016 at 1:06
• @200_success I think a is added once. Are you thinking of r += r + c*b?
– JS1
Jul 12, 2016 at 6:57
• @JS1 Yes, it's actually OK after all. Jul 12, 2016 at 6:59
• I'd add a bit of caching. Every time you calculate one element of the series, you could store that and use it instead of calculating it again. Jul 14, 2016 at 7:45
• What exactly are you saying? Can you explain. Jul 14, 2016 at 10:19

Performance

I tested your code, like so:

int r=0,c=1;
Deque<Integer> list = new ArrayDeque<>(1501);
for (int x = 0; x < 500; x++)
{
}
long start = System.nanoTime();
int t=list.pop();
for(int i=0;i<t;i++){
int a=list.pop();
int b=list.pop();
int n=list.pop();
r=a;
for(int j=0;j<n;j++){
if(j==0)
c=1;
else
c=c*2;
r= r +c*b;
System.out.print(r +" " );
}
System.out.println( );
}
long end = System.nanoTime();
System.out.println((end-start)+" nanos");


The resulting code prints "155156556 nanos", so took 155 milliseconds in total to run. I did a few more attempts and got durations in the range 120-145 millseconds.

When you say "have taken too much time to code the solution for this problem", did you mean "I took too long programming this"? Because there's no way to write code faster once it's written - the time has already been spent. 155 milliseconds for the largest inputs, for me, is fast enough.

I do not see any real opportunities for performance improvements. You could, in theory, do this:

        r=a + b;
c = 1;
System.out.print(r + " ");
for(int j=1;j<n;j++){
c=c*2;
r= r +c*b;
System.out.print(r +" " );
}
System.out.println( );


This would skip one cycle from the loop and remove a branch. Testing this version gives no large difference, and I see durations in the 120-140 ms range as well. Basically, I think the current version you have is good enough.

If you do want to go FASTER, though, here's what you'd do:

Don't print any output. The resulting code runs within a millisecond. String concatenation and output buffers hate you big time. Using StringBuilder gets the calculations down to 80 ms, but then printing the result takes another 40 ms.

The code you have will run about as fast as things will go.

What you can improve on is readability. For one, I'd add spaces around operators:

int r = 0, c = 1;
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int i = 0; i < t; i++){
int a = sc.nextInt();
int b = sc.nextInt();
int n = sc.nextInt();
r = a;
for(int j = 0; j < n; j++){
if(j == 0)
c = 1;
else
c = c * 2;
r = r + c * b;
System.out.print(r + " ");
}
System.out.println();
}


Other things you could do is make use of += and *=:

            c *= 2;
r += c * b;


In case of c * 2, though, you could shift all the bits left by 1 space, as that results in "multiply by 2"...

c <<= 1;


But maybe that's hard to read for others, so I would stick with *=.

• ideone.com/6lScTy - if you want to play around with my version Jul 14, 2016 at 7:55