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

Question

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( );
        }
    }
}

Answer 1

Performance

I tested your code, like so:

int r=0,c=1;
Deque<Integer> list = new ArrayDeque<>(1501);
list.add(500);
for (int x = 0; x < 500; x++)
{
    list.add(50);
    list.add(50);
    list.add(15);
}
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.

Readability

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 *=.