How to Solve a Problem 4: Where is the number?

Ran into this problem on reddit, and figure I'd give this a try on how to solve it. 

I need to find which line a certain number is, like:

First Line - 1

Second Line - 2 3 4

Third Line - 5 6 7 8 9

Fourth Line -> 10 11 12 13 14 15 16

Fifth Line -> 17 18 19 20 21 22 23 24 25

Nth line - (...) 1969 (...)

What is N? 

Always study the data given, and find the pattern. We need to solve this with a program. 

In this case, the pattern is pretty obvious: the line ends in the square of the number. 5th line ends in 25 (5^2). 

So to get N, we take the square root of 1969, and it turns out to be 44.something. 

44*44 = 1936. 

So it's obvious that 1969 is on the NEXT line, N=45. 

But how do you do this programmatically? The original question called for Python, but we'll do this in JavaScript, as it's quite simple. 

We need to keep testing N and increment N until N^2 is larger than 1969. 

let bFound=false

let n=1

while (!bFound) {

    if ((n^2)>=1969) {

        bFound=true }

    else {

        n++ }

}

//n is now the answer

Bonus: I calculated the answer WITHOUT a loop. Can you find the formula? 

Comments

Post a Comment

Popular posts from this blog

Yet another take on recursion

Recursion is often one of the hardest things to "get" in programming, so when you have your "aha" moment, it's that much more amazing. Conceptually, it's not that hard to see, but how do you actually program one such?  First, realize that " recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem." Let us try something simple. Let's say... I want you to sum up the elements of an arbitrary array, let's call it arr. It can have any number of elements, and each element is an integer. For the purpose of this exercise, let's just say it's [1,2,3,4], but it can be any integer, and the array can be any valid size. And I want to you use recursion, not loop (no for or while or such statements).  Now, remember the definition: "solving a problem where the solution depends on the solutions to smaller instances of the same problem".  Let's call this function rsum (
Read more

Problem Solving for Programmers: a Neglected Topic?

How often have you heard this story... it may be you, or someone you knew in class...  This person has no problem picking up syntax of a new programming language and even got the quirks of the language down. But when it comes time to write an actual program for an assignment, s/he has ZERO ideas about how to proceed. Just completely blanks out. Attempts to help with hints like "you need a loop", "you need a variable for X" results in one or two lines of code... and nothing else. Sounds familiar? This programmer never actually learned to problem-solve. S/he can learn things by rote, knew all the syntax, keywords, commands, etc. But has no actual understanding of the material. S/he would do great in a quiz or test, but fail completely on projects (or essay questions, if it's not programming). To badly paraphrase Sherlock Holmes' "You see but you do not observe", what we have here is a case if "you recall but you do not comprehend". I
Read more

How to Solve a Problem, with Examples

One of the fundamental tasks of a programmer is how to solve a programming problem, based on the specifications. Here is my attempt to solve such a problem, finally arriving at a validated answer.  If you've been on hackerrank.com, you may have seen this problem before. It's Fraudulent Activity Notifications .  TL;DR: given an array of arbitrary length (let's say it can go to 1x10^6). Each number in the array is expenditures for each day... It can range from 0 to 200 (and is always an integer). You are also given a number "d", that's the number of days you need to LOOK BACK to calculate the window. You need the median value of that window. If the next value is larger than or equal to twice the median, client is notified. Now, given arbitrary d, how many notifications had been generated, for a given array?  Example: you're given 6 4     10 20 30 40 50 60 6 is the size of the array: 6 entries. Window size is 4. First run, "10 20 30 40" Med
Read more