Riddle #923

logicmath

Two words are anagrams if and only if they contain the exact same letters with the exact same frequency (for example, "name" and "mean" are anagrams, but "red" and "deer" are not). Given two strings S1 and S2, which each only contain the lowercase letters a through z, write a program to determine if S1 and S2 are anagrams. The program must have a running time of O(n + m), where n and m are the lengths of S1 and S2, respectively, and it must have O(1) (constant) space usage.
First create an array A of length 26, representing the counts of each letter of the alphabet, with each value initialized to 0. Iterate through each character in S1 and add 1 to the corresponding entry in A. Once this iteration is complete, A will contain the counts for the letters in S1. Then, iterate through each character in S2, and subtract 1 from each corresponding entry in A. Now, if the each entry in A is 0, then S1 and S2 are anagrams; otherwise, S1 and S2 aren't anagrams. Here is pseudocode for the procedure that was described: def areAnagrams(S1, S2) A = new Array(26) A.initializeValues(0) for each character in S1 arrayIndex = mapCharacterToNumber(character) //maps "a" to 0, "b" to 1, "c" to 2, etc... A[arrayIndex] += 1 end for each character in S2 arrayIndex = mapCharacterToNumber(character) A[arrayIndex] -= 1 end for (i = 0; i < 26; i++) if A[i] != 0 return false end end return true end
79.34 %
46 votes

Similar riddles

See also best riddles or new riddles.

logicmath

There are 1 million closed school lockers in a row, labeled 1 through 1,000,000. You first go through and flip every locker open. Then you go through and flip every other locker (locker 2, 4, 6, etc...). When you're done, all the even-numbered lockers are closed. You then go through and flip every third locker (3, 6, 9, etc...). "Flipping" mean you open it if it's closed, and close it if it's open. For example, as you go through this time, you close locker 3 (because it was still open after the previous run through), but you open locker 6, since you had closed it in the previous run through. Then you go through and flip every fourth locker (4, 8, 12, etc...), then every fifth locker (5, 10, 15, etc...), then every sixth locker (6, 12, 18, etc...) and so on. At the end, you're going through and flipping every 999,998th locker (which is just locker 999,998), then every 999,999th locker (which is just locker 999,999), and finally, every 1,000,000th locker (which is just locker 1,000,000). At the end of this, is locker 1,000,000 open or closed?
Locker 1,000,000 will be open. If you think about it, the number of times that each locker is flipped is equal to the number of factors it has. For example, locker 12 has factors 1, 2, 3, 4, 6, and 12, and will thus be flipped 6 times (it will end be flipped when you flip every one, every 2nd, every 3rd, every 4th, every 6th, and every 12th locker). It will end up closed, since flipping an even number of times will return it to its starting position. You can see that if a locker number has an even number of factors, it will end up closed. If it has an odd number of factors, it will end up open. As it turns out, the only types of numbers that have an odd number of factors are squares. This is because factors come in pairs, and for squares, one of those pairs is the square root, which is duplicated and thus doesn't count twice as a factor. For example, 12's factors are 1 x 12, 2 x 6, and 3 x 4 (6 total factors). On the other hand, 16's factors are 1 x 16, 2 x 8, and 4 x 4 (5 total factors). So lockers 1, 4, 9, 16, 25, etc... will all be open. Since 1,000,000 is a square number (1000 x 1000), it will be open as well.
82.08 %
68 votes
logicmathstory

A swan sits at the center of a perfectly circular lake. At an edge of the lake stands a ravenous monster waiting to devour the swan. The monster can not enter the water, but it will run around the circumference of the lake to try to catch the swan as soon as it reaches the shore. The monster moves at 4 times the speed of the swan, and it will always move in the direction along the shore that brings it closer to the swan the quickest. Both the swan and the the monster can change directions in an instant. The swan knows that if it can reach the lake's shore without the monster right on top of it, it can instantly escape into the surrounding forest. How can the swan succesfully escape?
Assume the radius of the lake is R feet. So the circumference of the lake is (2*pi*R). If the swan swims R/4 feet, (or, put another way, 0.25R feet) straight away from the center of the lake, and then begins swimming in a circle around the center, then it will be able to swim around this circle in the exact same amount of time as the monster will be able to run around the lake's shore (since this inner circle's circumference is 2*pi*(R/4), which is exactly 4 times shorter than the shore's circumference). From this point, the swan can move a millimeter inward toward the lake's center, and begin swimming around the center in a circle from this distance. It is now going around a very slightly smaller circle than it was a moment ago, and thus will be able to swim around this circle FASTER than the monster can run around the shore. The swan can keep swimming around this way, pulling further away each second, until finally it is on the opposite side of its inner circle from where the monster is on the shore. At this point, the swan aims directly toward the closest shore and begins swimming that way. At this point, the swan has to swim [0.75R feet + 1 millimeter] to get to shore. Meanwhile, the monster will have to run R*pi feet (half the circumference of the lake) to get to where the swan is headed. The monster runs four times as fast as the swan, but you can see that it has more than four times as far to run: [0.75R feet + 1 millimeter] * 4 < R*pi [This math could actually be incorrect if R were very very small, but in that case we could just say the swan swam inward even less than a millimeter, and make the math work out correctly.] Because the swan has less than a fourth of the distance to travel as the monster, it will reach the shore before the monster reaches where it is and successfully escape.
81.89 %
53 votes
logicmath

Can you arrange four 9's and use of at most 2 math symbols, make the total be 100?
99 / .99 or 99 + 9/9
81.26 %
44 votes
logicmath

A women walks into a bank to cash out her check. By mistake the bank teller gives her dollar amount in change, and her cent amount in dollars. On the way home she spends 5 cents, and then suddenly she notices that she has twice the amount of her check. How much was her check amount?
The check was for dollars 31.63. The bank teller gave her dollars 63.31 She spent .05, and then she had dollars 63.26, which is twice the check. Let x be the dolars of the check, and y be the cent. The check was for 100x + y cent He was given 100y + x cent Also 100y + x - 5 = 2(100x + y) Expanding this out and rearranging, we find: 98y = 199x + 5 Which doesn't look like enough information to solve the problem except that x and y must be whole numbers, so: 199x ≡ -5 (mod 98) 98*2*x + 3x ≡ -5 (mod 98) 3x ≡ -5 ≡ 93 (mod 98) This quickly leads to x = 31 and then y = 63 Alternative solution by substitution: 98y = 199x + 5 y = (199x + 5)/98 = 2x + (3x + 5)/98 Since x and y are whole numbers, so must be (3x + 5)/98. Call it z = (3x+5)/98 so 98z = 3x + 5, or 3x = 98z - 5 or x = (98z - 5)/3 or x = 32z-1 + (2z-2)/3. Since everything is a whole number, so must be (2z-2)/3. Call it w = (2z-2)/3, so 3w = 2z-2 so z = (3w+2)/2 or z = w + 1 + w/2. So w/2 must be whole, or w must be even. So try w = 2. Then z = 4. Then x = 129. Then y = 262. if you decrease y by 199 and x by 98, the answer is the same: y = 63 and x = 31.
81.23 %
51 votes
cleanlogicmathsimple

Create a number using only the digits 4,4,3,3,2,2,1 and 1. So I can only be eight digits. You have to make sure the ones are separated by one digit, the twos are separated by two digits the threes are separated with three digits and the fours are separated by four digits.
41312432.
80.65 %
82 votes
logicmathsimple

Two trains are traveling toward each other on the same track, each at 60 miles per hour. When they are exactly 120 miles apart, a fly takes off from the front of one of the trains, flying toward the other train at a constant rate of 100 miles per hour. When the fly reaches the other train, it instantly changes directions and starts flying toward the other train, still at 100 miles per hour. It keeps doing this back and forth until the trains finally collide. If you add up all the distances back and forth that the fly has travelled, how much total distance has the fly travelled when the trains finally collide?
The fly has travelled exactly 100 miles. We can figure this out using some simple math. Becuase the trains are 120 miles apart when the fly takes off, and are travelling at 60 mph each, they will collide in exactly 1 hour. This gives the fly exactly 1 hour of flying time, going at a speed of 100 miles per hour. Thus, the fly will travel 100 miles in this hour.
80.15 %
61 votes