How to deal with large number inside of for loop in javascript?

Question

I am working on hacker rank problem. Repeated String [1] : https://www.hackerrank.com/challenges/repeated-string/problem

function main() {
    var s = readLine();
    var n = parseInt(readLine());
    var rep = 0;
    var repArray = []

//calculate each case 

  while(repArray.length < n){
      for(let j = 0; j < s.length; j++){
           if(repArray.length > n){
              break;
         }
          repArray.push(s[j])
      }
  }

  for(let a = 0; a < repArray.length; a++){
     if(repArray[a] === 'a'){
          rep++
      } 
  }
  console.log(rep)
}

I am receiving an error for the input a 1000000000000

the output of my code is <--- Last few GCs --->

1836 ms: Mark-sweep 597.4 (605.3) -> 359.7 (368.6) MB, 101.7 / 0.0 ms [allocation failure] [GC in old space requested].
1938 ms: Mark-sweep 359.7 (368.6) -> 359.7 (368.6) MB, 102.3 / 0.0 ms [allocation failure] [GC in old space requested].
2040 ms: Mark-sweep 359.7 (368.6) -> 359.7 (367.6) MB, 101.6 / 0.0 ms [last resort gc].
2142 ms: Mark-sweep 359.7 (367.6) -> 359.7 (367.6) MB, 101.7 / 0.0 ms [last resort gc].

<--- JS stacktrace --->

==== JS stack trace =========================================

Security context: 0x10178c2cfb51 2: main [/run-N6KBYU8cQzCneXKH0Tbm/solution.js:~30] [pc=0x2859725aec0] (this=0x10178c2e6119 ) 3: /* anonymous */ [/run-N6KBYU8cQzCneXKH0Tbm/solution.js:21] [pc=0x2859725717e] (this=0x2af8d3a77e81 ) 4: emitNone(aka emitNone) [events.js:91] [pc=0x28597256c33] (this=0x10178c204381 ,handler=0x2af8d3a78049 ,is...

the error of this code is

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory 1: node::Abort() [/usr/local/nodejs-binary/bin/node] 2: 0x1098b2c [/usr/local/nodejs-binary/bin/node] 3: v8::Utils::ReportApiFailure(char const*, char const*) [/usr/local/nodejs-binary/bin/node] 4: v8::internal::V8::FatalProcessOutOfMemory(char const*, bool) [/usr/local/nodejs-binary/bin/node] 5: v8::internal::Factory::NewUninitializedFixedArray(int) [/usr/local/nodejs-binary/bin/node] 6: 0xc4553f [/usr/local/nodejs-binary/bin/node] 7: v8::internal::Runtime_GrowArrayElements(int, v8::internal::Object**, v8::internal::Isolate*) [/usr/local/nodejs-binary/bin/node] 8: 0x285971079a7

Answer 1

It's a problem to find an efficient algorithm. You can't use brute force to solve these kinds of problems.

n is intentionally set to a high value so that you don't try to brute force. 10^12 is 1 Trillion, even if you could run each iteration of your loop in one nano second it would take 1000 seconds, which is long given that it's impossible to run each iteration in one nano second.

Problem that you're facing is because of the Space complexity, you're trying to store (n=10^12) (Max value) characters in memory. If each character takes 1 byte then the size of memory that we need is

10^12 bytes = 1000 Giga bytes = 1 Terra byte

I'm sure that your program won't be given that memory. Given there must other people trying to solve this problem at the same time. Hackerrank can't give this much resource to all of them.

Problem never intended for you to store this value in memory. Intention is for you to find a clever way of solving it without needing to store all the values.

Now clever way is that you can count how many as are in s. Now all you have to do is find out how many strings s you can repeat if you have only n characters.

Spoiler below (click/hover to view the answer):

That can be caculated by Math.floor(n / s.length). Now there may be some remaining string at the end which has length n % s.length. So the solution would be count = Math.floor(n / s.length) * CountAsIn(s) + CountAsIn(s.substring(n % s.length))

Answer 2

function getAOcc (s) {
  return s.match(/a/g)?.length || 0;
}

function repeatedString(s, n) {
  // Write your code here
  let stringLength = s.length;
  let aOcc = 0;
  const actualAOcc = getAOcc(s);
  
  if (!actualAOcc) return 0;
  
  const totalRep = Math.floor(n / stringLength);
  
  aOcc = actualAOcc * totalRep;
  
  const modS = n % stringLength
  if (modS > 0) {
      aOcc += getAOcc(s.substring(0, modS));
  }
  
  return aOcc;
}