0
\$\begingroup\$

I was trying to solve The Simplest Sum from hackerrank. Could anyone please let me know how I can make this code much effective in terms of time and space complexity?


You are just learning to code and are finished with loops and functions. Now, you are given the following pseudocode:

/*
 * The function has two integer parameters: k and n
 * The function returns the value of sum
 */
function f(k, n) {
    sum = 0;

    for (i = 1; i ≤ n; i += 1) {
        sum += i;
        i *= k;
    }

    return sum;
}

For three given integers k, a, and b, find the value of S mod (10⁹ + 7), where S is defined as:

$$S=\sum_{n=a}^b f(k,n)$$

Input Format

The first line of the input is an integer Q, the total number of queries. Each of the next Q lines contains three space separated integers k, a, and b.

Constraints

• 1 ≤ Q ≤ 10⁵
• 2 ≤ k ≤ 10⁵
• 1 ≤ ab ≤ 10^18   Constraints left out from the problem description as quoted in 2018

Output Format

For each query, print the value of S mod (10⁹ + 7) on a new line.

Sample Input

4
2 1 5
3 1 5
4 1 5
5 1 5

Sample Output

14
13
10
5

Explanation

  • Query 2 1 5

    f(2, 1) = 1
    f(2, 2) = 1
    f(2, 3) = 4
    f(2, 4) = 4
    f(2, 5) = 4
    

    So, S = f(2, 1)+f(2, 2)+f(2, 3)+f(2, 4)+f(2, 5) = 14

  • Query 3 1 5

    f(3,1) = 1
    f(3,2) = 1
    f(3,3) = 1
    f(3,4) = 5
    f(3,5) = 5
    

    So, S = f(3,1)+f(3,2)+f(3,3)+f(3,4)+f(3,5) = 13

  • Query 4 1 5

    f(4,1) = 1
    f(4,2) = 1
    f(4,3) = 1
    f(4,4) = 1
    f(4,5) = 6
    

    So, S = f(4,1)+f(4,2)+f(4,3)+f(4,4)+f(4,5) = 10

  • Query 5 1 5
    f(5,1) = 1
    f(5,2) = 1
    f(5,3) = 1
    f(5,4) = 1
    f(5,5) = 1
    
    So, S = f(5,1)+f(5,2)+f(5,3)+f(5,4)+f(5,5) = 5

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class maxSum {

static int simplestSum(int k, int a, int b) {
    int count = 1;
    int totalSum = 0;
    while(count <= b) {
        int z = maxSum(k, a);
        int mul = k*a;
        if(mul < b) {
            totalSum = totalSum + (z*(k*a));
        }else {
            totalSum = totalSum + (z*((b-count)+1));
        }

        count = count + (k*a);
        a = count;
    }
    return totalSum;
}

static int maxSum(int k , int a) {
    int sum = 0;
     for (int i = 1; i <= a; i += 1) {
         sum += i;
         i *= k;
     }
     return sum;
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int q = in.nextInt();
    for(int a0 = 0; a0 < q; a0++){
        int k = in.nextInt();
        int a = in.nextInt();
        int b = in.nextInt();
        int result = simplestSum(k, a, b);
        System.out.println(result);
    }
    in.close();
   }
}
\$\endgroup\$
2
  • \$\begingroup\$ (Welcome to CR!) It would be appropriate to name the origin of this problem statement and may be helpful to provide a link (there is a grey area in the formula?!). With a successfully designed "mathematical programming problem", no amount of cleverness in coding a brute force approach should be fast enough: you need a better algorithm. \$\endgroup\$
    – greybeard
    Jan 28 '18 at 23:07
  • \$\begingroup\$ @greybeard Please , find the link for problem statement hackerrank.com/contests/hackerrank-hiring-contest/challenges/… . I understand brute force approach is not the best one for this but i am not sure about other algorithm for this problem . \$\endgroup\$ Jan 29 '18 at 4:24
1
\$\begingroup\$

(I do not intend to address the better algorithm angle beyond stating that this is another hackerrank problem seeking the series for a sequence and quoting one advice: Pen down a few iterations yourself and you will find a way to compute the function value directly.)

Following the code presented top to bottom:

  • Document/comment your code. In the code.
    What is the class about, each method, its parameters?
  • Don't specify sweeping includes you don't use.
    Here, just use java.util.Scanner and not a single include
  • Class names should be CamelCase: class SimplestSum
  • provided arithmetic assignment operators and conditional expressions, I'd code accumulating
    totalSum += z * (mul < b ? k*a : (b-count)+1);
  • you introduce a variable for k*a, but use it in one place out of three, only.
  • at the end of simplestSum()'s code, I think it does try and use a series: explain in the method comment.
    Accumulation may exceed the range of int (applies to maxSum() as well)
  • maxSum()'s indentation is off ever so slightly
  • maxSum() does not try and use a series
  • do not open code closing AutoCloseables: use try-with-resources
  • in main(), using single letter variable names from the problem statement suggests itself - not so for nQueries.
    And why introduce another variable, why name it a0 (instead of query or even q (OK for an iteration variable in an inner loop, especially when not used otherwise))
  • a and b are input using java.util.Scanner.nextInt() where the Constraints allow ≤ 10^18
    depending on where and how large inputs are handled, this will necessitate declaring variables/parameters to handle numbers beyond the range of int more likely than not.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.