# Find nth digit in the infinite sum

ama trying to speed up solution for this: https://www.codewars.com/kata/59f6e1af3640ce12510000ad/train/javascript

last time I’ve searched digits with building giant strings and failed tests for n = `100000000`

Now I figured how to avoid building giant strings(see below).
and now I am failing last test for `n === 1000000000`

So I need to speed up more.

Where do I go from here?

I see possible problems:

I am still doing some stuff with every next number - parsing to string. Don’t know how to avoid that.

I am using two functions rn - the one below, and very similar func to get digits from square sequence. I can probably bake one function from those two, but not sure if it’ll help with perfomancy stuff.

To figure out function behaviour, use tests at the very bottom.

If anyone will want to look at the whole current version of my solution or more context is needed, I can provide. Not doing it right away, since the post is becoming long already.

``````const getDigitsFromNatSequence2 = (n) => {

let sequenceLength = 0;
let currentNumber = 1;
let currentNumberAsString;

while (sequenceLength <= n + 1) {
currentNumberAsString = currentNumber.toString();
if (sequenceLength + lengthToAdd >= n + 1) {
//this block should fire WHEN required digit
// somewhere in the current Number
// console.log(currentNumber);

let digit = currentNumberAsString
let digitPosInSequence = sequenceLength;
let digitPosInNumber = 0;

while (digitPosInSequence !== n) {
digitPosInNumber++
digitPosInSequence++
digit = currentNumberAsString[digitPosInNumber];
}
// after the above loop digit with position n should be
// assigned to digit
// console.log(digit)

// for getting digit on n + 1 position >>>
// different steps depending on
// do we need to get next number or not
nextDigit = digitPosInNumber !== lengthToAdd - 1
? currentNumberAsString[digitPosInNumber + 1]
: (currentNumber + 1).toString();
return [Number(digit), Number(nextDigit)];
}
currentNumber++;
}
return 'some stuff definitely went wrong if we not return early'
}
``````

here goes the test for this utility

``````let natSequence = "";
for (let i = 1; i < 100; i++) {
natSequence += i;
};
// console.log(natSequence)

// for n === x >>> results should be [natSequence[x], natSequence[x + 1]]

for (let n = 0; n < 20; n++) {
console.log(`CASE n === \${n}`);
console.log(`EXPECTED:`);
console.log([Number(natSequence[n]), Number(natSequence[n + 1])])
console.log(`RESULT:`);
console.log(getDigitsFromNatSequence2(n));
console.log(`***************`);
};

``````

Man, you peaked my curiosity, but also killed my entire evening. I’ve only recently started doing challenges on that site.

I didn’t skim your answer, but rather went to the site to attempt it on my own. I have been attempting the challenge and like you, was stuck unable to get that last test not to time out…until about 10 mins ago.

I finally got the 1000000000 to pass. Thought I could finally go to bed, until I clicked the final `attempt` button to complete the challenge and found that even after all that there are yet additional test which I’m now timing out on (spoiler alert).

Now like you I’m stuck. Skimmed your code above, and you and me approached the problem similarly. I’ve shaved it down best I could including coming up with a way to calculate the square through summation as I go rather than multiplying large numbers, and also looked up a way to calculate length without converting to string. All the loop does now is increment, sum the number length, and if bottom number not yet reached either does the square and its length. Any other relevant code only happens once the index is reached, so not inside the loop. There are two booleans to check if index is reached… not sure if the speed of those is relevent through thousands of iterations, but can’t think of a way to take them out. Not sure what I’m missing, but there must be some magic algorithm that doesn’t require looping all the way up to the answer one number at a time.

Sorry, not much help, just wanted to let you know I’m now sharing in your pain… thanks for that, ugh.

1 Like

I have some idea how to index into sequence of natural numbers much more faster than I am doing in the code above, without doing `num++` thing
Rn I am on the pen&paper stage, but looks promising.

I am gonna use this, my little research so far:

``````// RESEARCH ONLY >>> generate subSequence of n-digit nums
const generateSubSequence = (numberOfDigits) => {
const start = Math.pow(10, numberOfDigits - 1);
const end = Math.pow(10, numberOfDigits) - 1;
let result = "";
for (let i = start; i <= end; i++) {
result += i;
}
return result;
};
// generateSubSequence(1) >>> '123456789'

const subSeqLength = {};

for (let i = 1; i < 7; i++) {
subSeqLength[i] = generateSubSequence(i).length;
}

console.log(subSeqLength);
// key >>> size of digit
// value >>> total length of subsequence
// example >>> length of sequence of 1-digit numbers '123456789' equals 9
// { '1': 9, '2': 180, '3': 2700, '4': 36000, '5': 450000, '6': 5400000 }
``````

From here it can be seen, that infinite sequence of numbers
consists of subsequences of 1-digit numbers, 2-digit numbers, 3-digit numbers… so on
and
length of 1-digit numbers subsequence - 9 * 10^0 *1
length of 2-digit numbers subsequence - 9 * 10^1 *2
length of 3-digit numbers subsequence - 9 * 10^2 *3

Pattern is obvious and can be used to find subsequence where `n` belongs

Then

assume we know that `n` somewhere in the 3-digit numbers
we know `amount of 3 digit numbers`
we know `total number of digits in 3-digit numbers`
we know that subsequence of 3-digit numbers consists of similar chunks (well, 3-digits numbers lol)
and knowing all that we can search for specific number where `n` belongs

So that’s where I am, now need to code it and test stuff.

I’ve done that, I know this thingie from solving one of the euler probs. You used the fact that
1 + 3 = 4
4 + 5 = 9
9 + 7 = 16

So you have dynamic step(3, 5, 7, 9, 11…), to generate next square, right?
I think it helped to speed up, comaprative to usage of `**` or Math.pow, but iirc impact wasn’t much.

I think I need to share my whole plan, cause the above is all about subtask, not the whole challenge.
So, to clarify, order of operations:

for given ‘n’:

• find nth digit in sequence of natural numbers
• find (n + 1)th digit in sequence of natural numbers
• find nth digit in sequence of square numbers
• find (n + 1)th digit in sequence of square numbers

Knowing those 4, the main step of finding nth digit in the sum comes down to arithmetics.

I am getting further regarding searching inside natural numbers.
No nasty looping so far=)

``````// PERFOMANCE EFFORT

const getSubSequenceSize = subSequence => 9 * Math.pow(10, subSequence - 1) * subSequence;

const getNthDigitFromNaturals = (n) => {
// according to task, indexes in sequence are zero-based, but it is easier to proceed as if it is 1-based
const position = n + 1;
let previousLength = 0;
//subsequence = 1 >>> means n somewhere in 123456789; subsequence = 2 >>> means n somewhere in 10...99
let subSequence = 1;
while (position > getSubSequenceSize(subSequence) + previousLength) {
previousLength += getSubSequenceSize(subSequence);
subSequence++;
};
// console.log(subSequence, previousLength);
// at this point we know where n belongs: 1-digit, 2-digit or whatever n-digit subsequence
const positionInSubSequence = position - previousLength;
// further step >>> find which number holds nth digit
const nthNumberInSubSequence = Math.ceil(positionInSubSequence / subSequence);
// console.log(nthNumberInSubSequence);
// NOW we need to find 2 things - position of digit in the number(idea - use subtraction)
// - the number itself(idea - seem to be the case for binary search???)
}

for (let i = 0; i < 25; i ++) {
console.log(i)
getNthDigitFromNaturals(i);
console.log('*'.repeat(15));
}
``````

Seems like good work. Saw something similar, but my brain twisted into a knot at 1am while I tried to get the logic straight in my head. Thats probably the way to go though.

A little more optimization and my code did manage not to time out (about once in every 10 runs), but ran into another issue… I’ll leave it as a surprise… so haven’t managed to pass yet, and am going to let it fester for a day or so before going back to it.

Yeah, I calculated square as a running sum… previous_square + current_index + current_index - 1, pretty much same as yours above… not sure its a whole lot faster as summing large numbers was part of the problem anyway. The biggest savings was calculating the length rather than converting to string… who knew that was so expensive, as well as the Math.ceil()… pricy.

Wonder if anybody has a site that actually lists all Javascript functions, and the relative time it takes to run them. Went down a rabbit hole last night regarding execution cost differences between == and === expressions, as well as between null, false, and undefined comparisons, all trying to speed up my boolean expressions. These problems are frustrating, but sure am learning a lot regarding machine cycles and the cost of certain operations.

The gap between 4kyu and 3kyu problems on that site is a wide one it seems.

The difficulty level of probs is a bit arbitrary there. I don’t know much about how it is evaluated, iirc it is something like voting from community members.

I was able to come up with a function which will do
`only 8 iterations` for `n === 1000000000`
and finds nth digit. But the huge problem is - it is only for natural numbers sequence, that one 1234567891011…

I don’t know how to apply similar approach to squares sequence yet, if it is possible at all.

I tried to pass tests with efficient function for nat. nums, and old inefficient for squares - still no go lol

1 Like

I would not really try to pick == vs === for performance.

I think the idea is being able to index into the sequence of squares

Yeah, just cutting weight… the loop to index into the squares runs hundreds of thousands of times, and works except the test times out (intentionally) at 12000ms. My loop increments the num, the square, sums lengths, then has two booleans to see if the index has been reached (one is in the while loop, the other in an if statement).

I was reading it can make a big difference because == does a lot of type checking and type conversions during the comparison depending on value vs ===. Also read that undefined takes a lot more interations to conclude equality vs null. Again, all late night forum skimming, but did seem to shave off up to 5000ms on average checking === against null vs == against undefined… a conclusion derived late night in a non-consistent varying environment, so I could definitely be wrong. I was just chasing an idea that almost seemed to have merit. Also played with the loop, debating if a while loop would be the fastest compared to others(didn’t seem to make much difference). Only attacking the booleans because I thought I’d shaved as much off the other stuff as I can.

I really should build myself a small program to more consistantly check such things.

The differences between == and === don’t fix the underlying complexity of the code though.

I haven’t done any math research on the web regarding squares, but I have original thought:
we definitely know that the smallest 3-digit square is 10^2
the smallest 5-digit square is 10^4
so on
Maybe something will come up from that, need to think more.

This problem seems to be very mathy by nature, that’s why I am digging math first, not language quirks

That seems like a tractable angle.

Yeah… but the code works… and with these optimizations I am now able to complete the test without it timing out… just one more problem to solve… the surprise… and then the challenge is complete… it kinda rhymes with “him and her undertow”, lol.

I mean, I might just be attacking this completely wrong… but I’m seeing some light at the end of the tunnel by just shaving weight… although the light might just be an LED taped to a brick wall of frustration in the end.

I get that you are ‘shaving weight’. My point is that tackling miniscule differences between === and == isn’t going to make a big difference. You need to reduce the number of calculations overall required and not how those calculations are represented.

Microoptimizations are interesting but they don’t shave off very much time.

Yeah, my biggest concern about this approach was once you figure the appropriate length, how do you calculate a particular integer at that exact length once your there… I probably just can’t see it yet though.

According to my digging here https://oeis.org/A000290/b000290.txt

there is 9 squares, which are less than 100:
3 of them are 1-digit
6 of them are 2-digit
total 9

there is 90 squares, which are more or equal than 100, but less than 10000:
22 of them are 3-digit
68 of them are 4-digit
total 90

there is 900 squares, which are more or equal than 10000, but less than 1000000:
217 of them are 5-digit
683 of them are 6-digit
total 900

If only I would have an idea, what is the exact proportion of
5 and 6 digit squares inside their common bunch.
Like I can easily figure out that, ther is 900 total.
But how to compute, that there is 217 of 5th digits and 683 of 6-digits inside the bunch lol

holy moly, I can just Math.sqrt(1000) and Math.sqrt(100000) to find borders.
need to code now

UPDATE.

passing all stuff like a lightning bolt perfomance-wise now

but apparently there are some edge cases, discovered them in random tests=)
some results has decline from expected value - need to explore more