HackerRank "Digit sum" challenge

Question

Here's the question:

    Scanner scanner = new Scanner(System.in);   
    long x = scanner.nextLong();
    
    
    if(x<=1) return;
    if(x>=Math.pow(10, 12)) return;
    
    Map<Integer, Long> y = new HashMap<Integer, Long>();
    long k = 5;
    long yes = 0;
    
    for(int f = 0;f<x; f++){
    y.put(f, k);
    k++;
    
    
    if(k==7){
        k=1;
    }
        yes+= y.get(f);
    if(f == x-1){
        System.out.println((long)yes);
    }
        
    } 
//     for (int g = 0; g<y.size(); g++) {
//   yes+= y.get(g);
// } System.out.println((long)yes);
    
    
    
    
        
}}

The first time I was using ArrayList instead of HashMap. I changed it yet it keeps giving me the error. I even tried combining the loop as you can see from the commented out code.

The code works for the first few test cases but after it got into the 7+ digits (~2500000) it starts timing me out.

Please go easy on me as I just started learning Java a few days ago but I have decent JavaScript knowledge.

Do provide me tips on how to increase code efficiency in the future if I ever run into this again.

Answer 1

Your algorithm, which works one digit at a time, can be switched to one that's much more efficient.

See what happens if you divide the long string of digits into blocks of 6:

561234 561234 561234 561234 561234 561234 …

Each of those blocks has the same sum, so we can add them all up quite easily:

sum = x / 6 * 21;

For the partial block remaining, we could use a simple look-up table:

static final int[] partial = new int[6]{ 0, 5, 11, 12, 14, 17 };
sum += partial[x % 6];

This solution scales much better, as we no longer need a loop.