Do I need math to solve this algorithm?

Problem description

Lilah has a string, s, of lowercase English letters that she repeated infinitely many times. Given an integer, n, find and print the number of letter a 's in the first n letters of Lilah’s infinite string. For example, if the string s = “abcac” and n = 10 , the substring we consider is “abcacabcac”, the first 10 characters of her infinite string. There are 4 occurrences of a in the substring.

I have a solution, but it only works when n is less than ten power to nine.

function repeatedString(s, n) {
    // poor way to test edge cases?
    if (s.length === 1) return s[0] === 'a' ? n : 0;

    let prefix = s;

    while (prefix.length < n) {
        prefix += prefix;
    }

    if(prefix.length > n) {
        const difference = prefix.length - n;
        prefix = prefix.slice(0, prefix.length - difference);
    }
    
    let counter = 0;

    for (let char of prefix) {
        if (char === 'a') counter++;
    }
    return counter;
}

if n is greater than 10 power to 8, then I get the following error Invalid string length I have a guess of why this is happening but let me ask, why does this happen? And what are my options when I’m dealing with such a large number?, are loops out of the question?

1 Like

If you try building the entire string, then you will run out of memory. A little bit of arithmetic will get you the answer much faster and without the memory issue.

How would you approach this with arithmetic?

If the letter a shows up twice in the given string and we repeat the given string 7 times, then how many letters a are in the larger string with the repetitions?

the string has length x, if you need the first n letters, the string will be repeated n/x times. Inside the string the letter a appears m times, so I can find how many times it appear in the first n letters by […]

the math itself is pretty basic
I gave you a lot, you just need to complete the logic on your own

1 Like

Thanks, that looks way easier than I originally thought, it works for some cases, but I still need to deal with decimal numbers. For example:

repeatedString("abcac", 16); // expected ouput: 7

Following your instructions I came up with this (n/stringLength) * numberOfAs which gives me a decimal number for some cases. Taking the input from the example above, the output would be 6.4, Math.round would not work.

I’ve realized my math skills suck, what math courses would you recommend for a programmer? I’m just trying to be a decent programmer and I need to work on my math foundations, I don’t intend to be a mathematician either.

edit: I knew from the beginning that probably the best way to solve this algorithm was with math, I just couldn’t do it myself, so I’d like to improve my math skills.

You are pretty close with that formula. For whole numbers you have the problem solved.

What about this case?

s = "abcac"
n = 13

In this case we have the string
"abcacabcacabc"
or
"abcac|abcac|abc"

Does this help you see what you should do when you n isn’t perfectly divisible by the length of s?

you could try with the % reminder operator

1 Like

Regarding math courses – for most programmers, the best cost/benefit tradeoff is a basic (read undergraduate) course in discrete mathematics. That shouldn’t require much more than high school algebra as a pre-requisite and will be most directly applicable to problems like this one.

jrm

1 Like

What I see is that there are 2 remaining characters that are not a’s. I tried this:

const result = (n/stringLength) * numberOfAs;
const remainder = result % 1;

 return result - remainder;

But the algorithm still does not work for some cases, e.g.:
repeatedString("epsxyyflvrrrxzvnoenvpegvuonodjoxfwdmcvwctmekpsnamchznsoxaklzjgrqruyzavshfbmuhdwwmpbkwcuomqhiyvuztwvq", 549382313570) // output: 16481469407, expected output: 16481469408

Full code:

function repeatedString(s, n) {
     let numberOfAs = 0;
     for (let char of s) {
         if (char === 'a') numberOfAs++;
     }

     if (numberOfAs === 0) return 0;
     
     const stringLength = s.length;
     const result = (n/stringLength) * numberOfAs;
     const remainder = result % 1;
     console.log("result", result);
     console.log("remainder", remainder);
     return result - remainder;
}

Thanks, I will definitely take a look into that.

This line:
const remainder = result % 1;
doesn’t make much sense. Consider that n/1=n with remainder 0 \forall n.

I give up, I don’t intend to spend hours on this problem. I know I can only solve this with math and I need to work on my math skills, so I rather spend time on that.

If anyone has a solution please share it, I’d like to see it and the explanation if possible.

Thanks.

You are close. You have a formula that works when n is a multiple of s. To extend it isn’t too bad.

  1. Find how many letters a are in your string. (You have that, numberOfAs)
  2. Find how many full copies of your string you have. (You have that, n/stringLength, though you want to round down (floor))
  3. Find how many letters a are in those copies. (You have that, floor(n/stringLength) * numberOfAs)
  4. Find how many letters a are in the last few characters. (You don’t have this, but you have a way to compute it. If n = 14, and stringLength = 5, you have 14 % 5 = 4 last few characters to check.)

I wouldn’t say there is a lot of math here (personally). Its more breaking the problem down into pieces you can solve. You weren’t asked to make the string but rather count some letters. It turns out that counting is easier.