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.