Tag Archives: java

391. Prime-k factorial

For a prime p let S(p) = (∑(p-k)!) mod(p) for 1 ≤ k ≤ 5.

For example, if p=7,
(7-1)! + (7-2)! + (7-3)! + (7-4)! + (7-5)! = 6! + 5! + 4! + 3! + 2! = 720+120+24+6+2 = 872.
As 872 mod(7) = 4, S(7) = 4.

It can be verified that ∑S(p) = 480 for 5 ≤ p < 100.

Find ∑S(p) for 5 ≤ p < 108.

prime number of 5 ≤ p <100  = >  5, 7,  11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Case 1, assume p = 97if (p-k)!,  96! + 95! + 94! + 93!  + 92!, if use brute force method, factorial’s are very big number (infinite), time wise can’t possible to find out 108primes.
Advertisement

146,212. Die-game Yahtzee

This task is about the scoring in the first phase of the die-game Yahtzee, where five dice are used. The score is determined by the values on the upward die faces after a roll. The player gets to choose a value, and all dice that show the chosen value are considered active. The score is simply the sum of values on active dice.

Say, for instance, that a player ends up with the die faces showing 2, 2, 3, 5 and 4. Choosing the value two makes the dice showing 2 active and yields a score of 2 + 2 = 4, while choosing 5 makes the one die showing 5 active, yielding a score of 5.

Your method will take as input an int[] toss, where each element represents the upward face of a die, and return the maximum possible score with these values. Read more of this post

203. New Username

When a new member signs up, it is possible that she initially chooses the same username as an existing member. The system must then inform the new member of the conflict and suggest a variant of the chosen name with a number attached to the end.

If an existing member is named “FunkyMonkey”, for example, and a new member wants the same username, the simplest suggestion the system can make is “FunkyMonkey1”. If there is already a member by that name, the system must suggest “FunkyMonkey2”, unless that variant is also taken. If all names from “FunkyMonkey1” through “FunkyMonkey9” are taken as well as the original “FunkyMonkey”, the system moves on to consider “FunkyMonkey10”, and so on. The goal is to use the smallest possible number in the variant. Note that each username consists of letters (the characters from ‘a’ to ‘z’ and from ‘A’ to ‘Z’) and numerals (‘0’ to ‘9’).

You are given a String[], existingNames, containing all usernames that have already been registered in the system. You are also given a single String, newName, containing the username that a new member wants to use. In the event of a conflict, this member will accept the suggestion offered by your system in accordance with the principles above. Return a String containing the username finally assigned to the new member. Read more of this post

191. Betting Money

You run a gambling business in which people place bets on the margin of victory in a football game. At the end of the day, the company would like to know what the day’s net gain has been.   Just as in any other betting system, people place certain amounts as their bets and if they guess correctly, they get their money back plus a pre-specified percentage of their bet; otherwise they lose the money they bet.

You are given a int[], amounts, the ith element of which is the number of dollars people have placed on a victory margin of i (i = 0 refers to the first element). You are also given a int[], centsPerDollar, the ith element of which is the number of cents the company has to pay for every dollar the people bet on a victory margin of i, if the final outcome is a victory margin of i. Finally, you are given an int, finalResult, which is the final margin of victory. You have to determine what the net gain for the day was and return the amount in cents.

For example, if amounts were {10,20,30}, it would mean that people placed $10 on a draw outcome, $20 on a victory margin of 1 and $30 on a victory margin of 2, and if centsPerDollar were {20,30,40}, it would mean the people would win 20 cents per dollar bet if the match were a draw, 30 cents per dollar if the victory margin were 1 and 40 cents per dollar if the victory margin were 2.

Suppose the final result is a victory margin of 1 (i.e., finalResult = 1). Then the people who guessed the outcome as a margin of 0 or 2 were wrong and the company receives the amounts they bet, $10+$30. However, the people who guessed that the outcome would be a margin of 1 were correct, and they receive money from the company according to the amount they bet (20 dollars) and the pre-set payoff percentage (30 cents per dollar) . This amounts to 20*30 = 600 cents. Hence, the day’s net gain is 40 dollars – 600 cents = 3400 cents. You should return 3400. Read more of this post

209. Olympic Medal Table

The results of the disciplines are given as a String[] results, where each element is in the format  “GGG SSS BBB”. GGG, SSS and BBB are the 3-letter country codes (three capital letters from ‘A’ to ‘Z’)  of the countries winning the gold, silver and bronze medal, respectively.

The medal table is a String[] with an element for each country appearing in results. Each element has  to be in the format “CCO G S B” (quotes for clarity), where G, S and B are the number of gold, silver  and bronze medals won by country CCO, e.g. “AUT 1 4 1”. The numbers should not have any extra leading zeros.

Sort the elements by the number of gold medals won in decreasing order. If several countries are tied,  sort the tied countries by the number of silver medals won in decreasing order. If some countries are  still tied, sort the tied countries by the number of bronze medals won in decreasing order. If a tie  still remains, sort the tied countries by their 3-letter code in ascending Read more of this post

208. Tall People

A group of people stands before you arranged in rows and columns. Looking from above, they form an R by C rectangle of people. Your job is to return 2 specific heights – the first is computed by finding the shortest person in each row, and then finding the tallest person among them (the “tallest-of-the-shortest”); and the second is computed by finding the tallest person in each column, and then finding the shortest person among them (the “shortest-of-the-tallest”). Read more of this post

236. Business Tasks

N tasks are written down in the form of a circular list, so the first task is adjacent to the last one. A number n is also given. Starting with the first task, move clockwise (from element 1 in the list to element 2 in the list and so on), counting from 1 to n. When your count reaches n, remove that task from the list and start counting from the next available task. Repeat this procedure until one task remains. Return it. Read more of this post

92. Number Chain end at 1 or 89

A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before. For example, 44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89. How many starting numbers below ten million will arrive at 89? Read more of this post

95. Amicable chain

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → …)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million. Read more of this post

386. Antichain

Let n be an integer and S(n) be the set of factors of n.

A subset A of S(n) is called an antichain of S(n) if A contains only one element or if none of the elements of A divides any of the other elements of A.

For example: S(30) = {1, 2, 3, 5, 6, 10, 15, 30} , {2, 5, 6} is not an antichain of S(30).  {2, 3, 5} is an antichain of S(30).

Let N(n) be the maximum length of an antichain of S(n).  Find ΣN(n) for 1 ≤ n ≤ 108

Read more of this post

387. Harshad/Niven Number

A Harshad or Niven number is a number that is divisible by the sum of its digits.  201 is a Harshad number because it is divisible by 3 (the sum of its digits.). When we truncate the last digit from 201, we get 20, which is a Harshad number.  When we truncate the last digit from 20, we get 2, which is also a Harshad number.  Let’s call a Harshad number that, while recursively truncating the last digit, always results in a Harshad number a right truncatable Harshad number.

Also:  201/3=67 which is prime.
Let’s call a Harshad number that, when divided by the sum of its digits, results in a prime a strong Harshad number.

Now take the number 2011 which is prime.  When we truncate the last digit from it we get 201, a strong Harshad number that is also right truncatable.  Let’s call such primes strong, right truncatable Harshad primes.

You are given that the sum of the strong, right truncatable Harshad primes less than 10000 is 90619.

Find the sum of the strong, right truncatable Harshad primes less than 1014. Read more of this post

29.Distinct terms

Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100? Read more of this post

27.Quadratic Expression

Euler published the remarkable quadratic formula:   n² + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.

Using computers, the incredible formula  n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n  
e.g. |11| = 11 and |−4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0. Read more of this post

25.Fibonacci sequence to contain 1000 digits

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1   F2 = 1   F3 = 2   F4 = 3  F5 = 5  F6 = 8  F7 = 13  F8 = 21  F9 = 34  F10 = 55  F11 = 89  F12 = 144

The 12th term, F12, is the first term to contain three digits.  What is the first term in the Fibonacci sequence to contain 1000 digits? Read more of this post

23.Perfect, Deficient and Abundant Number

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number.  For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.  A number n is called deficient if the sum of its proper divisors is less than n (15=> 1+3+5=9) and it is called abundant  if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123  can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by  analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant  numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers. Read more of this post

21.Amicable numbers

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

Pythagoras when asked, “What is a friend”, replied that a friend is one “who is the other I” such as 220 and 284.  The numbers 220 and 284 form the smallest pair of amicable numbers (also known as friendly numbers) known to Pythagoras.

http://www.shyamsundergupta.com/amicable.htm

One simple rule given by Arab Thabit ibn Korrah in 9th century is given below:  Take any power of 2, such as 2n where n>1 and form the numbers   h = 3.2^n –1,    t = 3.2^n-1 –1,     s = 9.2^2n-1 –1

If h, t and s are all primes then 2^n ht and 2^n s are amicable.

For example when n=2, we get h=11, t=5 and s=71, which are all primes hence 2n h t = 220 and 2n s = 284 are amicable numbers.
Similarly when n = 4, we get the amicable pair (17296, 18416).

There is a possible ambiguity here: should both members of a pair be below 10000 or does the condition also include pairs (a,b) for which a<10000, but b not. If you displayed all pairs you found, you will have noticed that there is no such pair, so we will not bother. Read more of this post

22. Total of all the name scores in the file

Using names.doc (right click and ‘Save Link/Target As…’), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file? Read more of this post

Maximum cut

Kader only likes to eat eels of length exactly 10, no more, no less. Before she eats, she may cut the eels to prepare pieces of desired length. However, she only has the time to make at most maxCuts cuts. You are given a int[] eelLengths. Each element of eelLengths is the length of one of the eels Kader has at the beginning. You are also given the int maxCuts. Return the maximum number of eels of length exactly 10 she can produce.

Examples
1)i/p={13,20,13}, 2 Returns: 3
Steps are 13 = 13/10 = 1, exactly 10 length 10 is 1.
20 = 20/10 = 2, exactly 10 length is 2, total is 3. (reached maxcuts 2). Total is 3.

2)i/p={5, 5, 5, 5}, 2 Returns: 0
All are less then 10.

3)i/p={34, 10, 48}, 4 Returns: 5
Steps are 34 = 34/10 = 3 = 3 (maxcuts 5-3= 2)
10 = 10/10 = 1 = 4
48 = 48/10 – 4 = 1(exceed maxcuts 4>2)

4)i/p={30, 50, 30, 50}, 350 Returns: 16 Read more of this post

Minimum palindrome cost

A palindrome is a string that reads the same from left to right as it does from right to left.  The length of a input String s is even. Each character of s is either ‘o’, ‘x’, or ‘?’ Your task in this problem is to replace each occurrence of ‘?’ in s with either ‘o’ or ‘x’ so that s becomes a palindrome. You are also given integers oCost and xCost. Replacing ‘?’ with ‘o’ costs oCost, and replacing ‘?’ with ‘x’ costs xCost.     Return the minimum cost of replacing ‘?’s by ‘x’s and ‘o’s that turns s into a palindrome. If it is impossible to obtain a palindrome, return -1 instead.

Examples

1)i/p=”oxo?xox?”, 3, 5 Returns: 8
Steps are   s[7] = ? = > s[7] replace by ‘o’ of s[0]. s[7] = o, so cost is 3.
s[3] = ? = > s[3] replace by ‘x’ of s[4]. s[2] = x, so cost is 5. Total Cost is 8.

2)i/p=”x??x”, 9, 4 Returns: 8
Steps are  s[1] = s[2] = ? > both are replaced by minimum cost 4 is ‘x’. Total Cost is 8.

3)i/p=”ooooxxxx”,12,34 returns: -1
Steps are    No ‘?’ character, and s is not a palindrome. Total Cost is -1.

4)i/p=”oxoxooxxxxooxoxo”,7,4 Returns: 0
Steps are  No ‘?’ character, and s is already a palindrome. Total Cost is 0.

5)i/p=”?o”, 6, 2 Returns: 6
Steps are  s[0] = ? = > s[0] replace by ‘o’ of s[1]. s[0] = o, so cost is 6. Total Cost is 6. Read more of this post

Casket Of Star

The Casket of Star (sic) is a device in the Touhou universe. Its purpose is to generate energy rapidly. Initially it contains n stars in a row. The stars are labeled 0 through n-1 from the left to the right. You are given a int[] weight, where weight[i] is the weight of star i.The following operation can be repeatedly used to generate energy:

Choose a star x other than the very first star and the very last star.  The x-th star disappears.  This generates weight[x-1] * weight[x+1] units of energy.  We decrease n and relabel the stars 0 through n-1 from the left to the right.

Examples
1)i/p={1,2,3,4}   Returns: 12
Steps are
{1,2,3,4}
(3+4){1,3,4} | (8+4) {1,2,4}

2)i/p={100,2,1,3,100} Returns: 10400

3)i/p={2,2,7,6,90,5,9} Returns: 1818

4)i/p={477,744,474,777,447,747,777,474} Returns: 2937951

4)i/p={3, 1, 4, 10, 3} Returns: 51
{3, 4, 10, 3} = 12 (12+30+9=>51, 12+12+9=>33)
{3, 10, 3} = 30 | {3, 4, 3} = 12 = 9 | = 9
{3, 1, 10, 3} = 10 (10+30+9=>49, 10+3+9=>22)
{3, 10, 3} = 30 | {3, 1, 3} = 3 = 9 | = 9
{3, 1, 4, 3} = 12 (12+12+9=>33, 12+3+9=>24)
{3, 4, 3} = 12 | {3, 1, 3} = 3 = 9 | = 9 Read more of this post