Category Archives: Algorithm

what is the chance of the coin touched 2 colors.

One Diameter coin is thrown on to the 2 color squared (2 X 2) chessboard, what is the chance of the coin touched 2 colors.

Solution

Area of each square (2 X 2) = 4. (#1)

Area of inner square (1 X 1) = 1( #2)

Area of lined square = #1 – # 2 = 4 -1 = 3.

so total probability is 3/4 = .75 percentage

One coin diameter center is placed inside #2 square, possibility one color touch.

But if it in #2, possibility is 2 color touch (See green color).

Advertisement

The maximum distance cars can go problem

Total 16 cars with a tank that has the capacity to go 100 meter. All are started the same position with fully fuelled.

Find the maximum distance that you can go? No need all the cars to reach the final place.

Solution

Total Optimized distance reached 338.07 drop by every car in one ride.

Not a optimized solution, total distance is 300

3 House Water Connect Problem

Connect the 3 houses to their respective water tanks using pipes.

Rules

1 Pipes should not cross one another
2 Pipe should not cross the wall above house 2

Solution

Statistics

Type of statistics
Max – Largest value in L – sorting L(0)
Min – Smallest value in L – L[n-1]
Midpoint – average of max & min – (L[0]+L(n-1))/2
Mean -average of values in L
Mode – most common value in L
Median – “middle” value in L (half bigger, half smaller) – L(n/2)

Statistics by sorting list, all running time 0(1) (constant time)
Statistics on Unsorted list,
1.Sort first, running time 0(n log n) under the comparison model, like sorter
2.Extract the statistic in effectively one scan through the data, running time 0(n), like max, min, median
Read more of this post

Graphs

graph
Clustering Coefficient
clusting coefficient

The clustering coefficient for graph is just the average of the clustering coefficients of the nodes in the graph.
Read more of this post

Networks

Chain networks consist of a set of nodes and a sequence of edges between them connect them into a single chain.

chain ={}
for i in range(n-1):
    make_link(chain, i, i+1)
0——–0——–0——–0——–0
n1 e1 n2 e2 n3 e3 n4 e4 n5   – nodes (n), edges (e) = n-1
Read more of this post

Eulerian Tour & Path

# For example, if the input graph was
# [(1, 2), (2, 3), (3, 1)]
# A possible Eulerian tour would be [1, 2, 3, 1]

from collections import defaultdict
from random import choice
import itertools
def eulerian_tour(graph):
    tour=[]
    nodes=defaultdict(list)
    for s, e in graph:
        nodes[s].append(e)
        nodes[e].append(s)
    start = choice(nodes.keys())
    tour.append(start)
    while(len(nodes[start])>0):
        last = nodes[start].pop()
        tour.append(last)
        nodes[last].remove(start)
        start = last
    if list(itertools.chain(*nodes.values())):
        #print nodes
        for start in nodes:
            if start in tour and len(nodes[start])>0:
                index = tour.index(start)
                #print start, index, tour    
                while (len(nodes[start])>0):
                    last = nodes[start].pop()
                    nodes[last].remove(start)
                    index+=1
                    tour.insert(index, last)
                    start = last
                    #print tour
                    #print nodes
    return tour

graph = [(0, 1), (1, 5), (1, 7), (4, 5), (4, 8), (1, 6), (3, 7), (5, 9), (2, 4), (0, 4), (2, 5), (3, 6), (8, 9)]
eulerian_tour(graph)

Read more of this post

Analysis of algorithms

Mathematics of algorithms
1)Formalize what you’re doing
2)analyzing correctness
2)analyzing the efficiency

Measuring Times
Simplifying assumptions
1. a simple statement takes one unit of time (e.g. x = x + 1 => 1 unit)
2. a sequence of simple statement is the sum of the individual times (e.g. if y==4: z = z/2 => 2 units)
3. A Loop takes time equal to the body x iterations (e.g. for i in range(4): print i => 4 units)
Read more of this post

Graph, Eulerian Path, Eulerian Tour

Algorithms areGraph just how we organize computations to solve a particular problem. Some algorithms are really straightforward, but other algorithms take advantage of subtle mathematical properties to quickly and accurately provide an answer.

A set of circles and lines connecting between them is graph.
Read more of this post

Big-O notation

Big-O notation compactly describes the running time of an algorithm. An algorithm’s efficiency in terms of its worst-case running time, which is the largest amount of time an algorithm can take given the most difficult input of a fixed size

For example, if your algorithm for sorting an array of n numbers takes roughly n2 operations for the most difficult dataset, we say that the running time of your algorithm is O(n2).

In reality, any number of operations, such as 1.5n2, n2 + n + 2, or 0.5n2 + 1; all these algorithms are O(n2) because big-O notation only cares about the term that grows the fastest with respect to the size of the input.

A function f(n) is Big-O of function g(n), or O(g(n)), when f(n) ≤ c · g(n) for some constant c and sufficiently large n.

Big O notation is to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm. Read more of this post

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.

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