Apple and orange hackerrank

HackerRank: “Apple and Oranges” — Simple Solutions to Hard Problems

This problem stumped me quite well. The following is the problem:

The example given above was quite straightforward, allowing me to find a proper and well written algorithm as soon as I read it. Based on the explanation given by the question, here is the written algorithm to solve this problem:

1. Create two variables first, to keep the numbers of apple and oranges. For the sake of the tutorial, we will call them apple_landed and orange_landed .
2. Loop through the array apple.
3. For every element of the displacement the loop is currently in, add a (distance of the apple tree) to the element, so that it will be the proper displacement in relation to the default (because the displacement in the array is related to the distance between the fallen fruit and its respective tree). Assign this current value to a temporary variable.
4. After adding the distance of the apple tree to the current element of the loop, I should check if it lands on to the house. This can be done by writing another loop that it will iterate through the position of the house. For example, if the position of my house’s s is 7 and t is 10, it will iterate through 7,8,9, and 10.
5. If the temporary variable from the 2nd step is equal to one of the iterations from the 3rd step, then add 1 to the variable apple_landed.
6. Repeat step 1 to 5, but using orange tree this time.
7. Print apple_landed and orange_landed on two separate lines. Use «\n» to help with adding the new line.

That was my initial algorithm. From this algorithm, the following snippet is the algorithm translated to Python3 code:

However, it is silly to think that an algorithm can pass through all crazy test cases that the dear question maker had made. After running it for a single test case and got the green light, I tried to run the whole test case. It failed after succeeding in only 3 test cases, while the other failed cases resulted in a “Terminated due to timeout :(“ error.

A simple Google search showed that a Termination due to timeout error happens when the program runs at a much slower time than expected, which resulted in the program itself being terminated. Besides, who would want to run a slow program? Slow program sucks. This is why I breathe and live in code. I hate slow things. Things that aren’t efficient. I hate waiting. Waiting is the biggest waste of time, especially if it’s waiting for nothing. I aim to make things quicker. To solve problems no one could solve.

Enough with my bravado. The reason a program could run this slow is because of the use of arrays instead of Hash Maps. Huh, interesting enough. For once, I actually learned something from a mistake.

After searching through the ever helpful discussion bar for the first time, it turned out that another user experienced the same problem as me. A user pointed out that what causes the timeout is the algorithm step number 4. Paying my Hackos to see a locked test case revealed that a certain test case has a very high difference between s and t. Imagine iterating through each of those numbers, it would be too much for the computer to handle.

And so, another user proposed a solution, one that is way too simple that made me wonder why I couldn’t think of it in the first place. The solution is: replace iterating over the s and t, and instead see if the number is greater than/equal to s and lower than/equal to t. This is what the final answer looks like:

This small addition to the code passed all the test case.

And it hurts. It hurts and exciting at the same time. To see such simple solution to a problem that could hurt the runtime of a program. It hurts, because obviously I am lacking in proper skills. I haven’t been doing much exercises while all other people are probably banging their back bones over solving 10 algorithm problems a day.

Hopefully, I could apply this life lesson to advance my programming career.

Источник

Apple and Oranges HackerRank Solution in C, C++, Java, Python

Sam’s house has an apple tree and an orange tree that yield an abundance of fruit. Using the information given below, determine the number of apples and oranges that land on Sam’s house.

In the diagram below:

• The red region denotes the house, where is the start point, and is the endpoint. The apple tree is to the left of the house, and the orange tree is to its right.
• Assume the trees are located on a single point, where the apple tree is at point , and the orange tree is at point .
• When a fruit falls from its tree, it lands units of distance from its tree of origin along the -axis. *A negative value of means the fruit fell units to the tree’s left, and a positive value of means it falls units to the tree’s right.

Given the value of for apples and oranges, determine how many apples and oranges will fall on Sam’s house (i.e., in the inclusive range )?

For example, Sam’s house is between and . The apple tree is located at and the orange at . There are apples and oranges. Apples are thrown units distance from , and units distance. Adding each apple distance to the position of the tree, they land at . Oranges land at . One apple and two oranges land in the inclusive range so we print

Complete the countApplesAndOranges function in the editor below. It should print the number of apples and oranges that land on Sam’s house, each on a separate line.

countApplesAndOranges has the following parameter(s):

• s: integer, starting point of Sam’s house location.
• t: integer, ending location of Sam’s house location.
• a: integer, location of the Apple tree.
• b: integer, location of the Orange tree.
• apples: integer array, distances at which each apple falls from the tree.
• oranges: integer array, distances at which each orange falls from the tree.

The first line contains two space-separated integers denoting the respective values of and .

The second line contains two space-separated integers denoting the respective values of and .

The third line contains two space-separated integers denoting the respective values of and .

The fourth line contains space-separated integers denoting the respective distances that each apple falls from point .

The fifth line contains space-separated integers denoting the respective distances that each orange falls from point .

Print two integers on two different lines:

1. The first integer: the number of apples that fall on Sam’s house.
2. The second integer: the number of oranges that fall on Sam’s house.

Источник

Как правильно понять задачу «Apple and Orange» на hackerrank?

День добрый!
Добрался до задачи «Apple and Orange» на hackerrank и запутался в ее хитросплетениях.

В доме Сэма есть яблоня и апельсиновое дерево, которые дают обилие фруктов. На приведенной ниже диаграмме красная область обозначает его дом, где s-начальная точка, а t-конечная точка.

Яблоня находится слева от его дома, а апельсиновое дерево-справа.

Можно предположить, что деревья расположены в одной точке, где яблоня находится в точке a, а апельсиновое дерево — в точке b.

Когда плод падает со своего дерева, он приземляется на расстоянии d единиц от своего дерева вдоль оси x.

Отрицательное значение d означает, что плод упал слева от дерева, и положительное значение d означает, что он падает направо от дерева.

Учитывая значение d для m яблок и n апельсинов, определите, сколько яблок и апельсинов упадет на дом Сэма (т. е. в инклюзивном диапазоне [s,t)?

Например, дом Сэма находится между s=7 и t=10. Яблоня расположена на a=4, а апельсин на b=12.

Есть m=3 яблока и n=3 апельсина.

Яблони бросают яблоки на [2,3,-4] единицы расстояния от a, а апельсиновое дерево бросает апельсины на [3,-2,-4] единицы расстояния.

При добавлении каждой дистанции яблока до положения дерева, они приземляются на [4+2,4+3,4-4]=[6,7,0]

Участок падения на землю апельсинов [12+3,12-2,12-4]=[15,10,8]

Одно яблоко и два апельсина земли в диапазоне 7-10, так что мы печатаем

Откуда взялись [2,3,-4] и [3,-2,-4]?
Похоже что в задаче недописано

Источник

Hackerrank challenge — Apple and Orange

The problem I am trying to solve is this. Apples fall at various offsets relative to an apple tree at position a, and oranges fall at various given offsets relative to an orange tree at position b. How many of each kind of fruit lie between positions s and t?

I pass 8 from the 11 test cases, I fail 3 tests due to timeout error.

I spent the last hour or so trying to refactor my code to make it faster but I am out of ideas now. Can someone give an advice what should I do in order to make it faster?

3 Answers 3

Just a few if statements will do.

Your answer to the problem is rather strange.

To find out if an apple or orange is between s and t is just a simple if statement.

So you only need to loop over the apples and oranges once. Best is to have a single loop that does both the apples and oranges at the same time, then a second loop to do the remaining (if any) fruit.

There is no need to create any arrays. Your solutions is exponentially lots more work than is needed. For speed aim to reduce the number of times your code loops. Note that Array.map is the same as doing a for loop over each item, but much slower in this case.

_{NOTE I struck out exponentially and added «lots» as some have complained, I used it in the common vernacular (increasing rate of change) and not as in CS time complexity.}

Your code loops over the length of the house, then the number of apples and oranges, and then you loop the length of the house times the number of apples plus oranges.

If the house is 5 units wide and there are 5 of each fruit you iterate over them a total of (house pos to array) 5 + (map each fruit array) 5 + 5, (counting) 5 * (5 + 5) for a total of 65 iterations. This is 60 times too many.

Example

I have not run this code so there could be a few typos, but the general structure is as described above.

This is faster than your solution, If it is fast enough to pass the test I do not know.

Источник

SL TECH ACADEMY

Apple and Orange – HackerRank Solution

Problem :

Sam’s house has an apple tree and an orange tree that yield an abundance of fruit. In the diagram below, the red region denotes his house, where s is the start point, and t is the endpoint. The apple tree is to the left of his house, and the orange tree is to its right. You can assume the trees are located on a single point, where the apple tree is at point a , and the orange tree is at point b .

When a fruit falls from its tree, it lands d units of distance from its tree of origin along the x -axis. A negative value of d means the fruit fell d units to the tree’s left, and a positive value of d means it falls d units to the tree’s right.

Given the value of d for m apples and n oranges, determine how many apples and oranges will fall on Sam’s house (i.e., in the inclusive range [s, t] )?

For example, Sam’s house is between s = 7 and t = 10. The apple tree is located at a = 4 and the orange at b = 12 . There are m = 3 apples and n = 3 oranges. Apples are thrown apples = [2, 3, -4] units distance from a , and oranges = [3, -2, -4] units distance. Adding each apple distance to the position of the tree, they land at [4 + 2, 4 + 3, 4 + -4] = [6, 7, 0] . Oranges land at [12 + 3, 12 + -2, 12 + -4] = [15, 10, 8] . One apple and two oranges land in the inclusive range 7 — 10 so we print

Function Description :

Complete the countApplesAndOranges function in the editor below. It should print the number of apples and oranges that land on Sam’s house, each on a separate line.

countApplesAndOranges has the following parameter(s):

• s: integer, starting point of Sam’s house location.
• t: integer, ending location of Sam’s house location.
• a: integer, location of the Apple tree.
• b: integer, location of the Orange tree.
• apples: integer array, distances at which each apple falls from the tree.
• oranges: integer array, distances at which each orange falls from the tree.

Input Format :

The first line contains two space-separated integers denoting the respective values of s and t .
The second line contains two space-separated integers denoting the respective values of a and b .
The third line contains two space-separated integers denoting the respective values of m and n .
The fourth line contains m space-separated integers denoting the respective distances that each apple falls from point a .
The fifth line contains n space-separated integers denoting the respective distances that each orange falls from point b .

Constraints :

Output Format :

Print two integers on two different lines:

1. The first integer: the number of apples that fall on Sam’s house.
2. The second integer: the number of oranges that fall on Sam’s house.

Источник