Euclid’s algorithm: gcd of 2 number equals gcd of smaller number and their difference. Use Euclid’s algorithm to calculate gcd(a, b). package com.pli.project.algorithm.gcd; import java.math.BigInteger; /** * Created by lipeng on 2015/5/23. */ public class Gcd { /** * Keep a is the max value. * gcd{a,b}=gcd{−a,b}=gcd{a,−b}=gcd{−a,−b} * https://proofwiki.org/wiki/GCD_for_Negative_Integers */ public static int gcd(int a, int… Read More »
Given a number n, find the smallest number that has same set of digits as n and is greater than n. If x is the greatest possible number with its set of digits, then print “not possible”. examples: input: 1111 output: not possible inout: 1234 output: 1243 input: 12345765 output: 12346557 Solution: Assume the input… Read More »
This question is from careercup. link Problem description: Write a function that receives a stream of pairs: id (some unique integer) + weight (positive real number). The stream ends with the special pair {0,0}. The function should return one the unique ids at random, with probability proportional to its weight (compared to the total weights… Read More »
Evolve the problem to 2-dimension array. There is a matrix, m x n. Several groups of people locate at some certain spots. In the following example, there are three groups and the number 4 indicates there are four people in this group. Now we want to find a meeting point in the matrix so that… Read More »
Problem description: You are given n candles with size of each candle present as an element in an integer array i.e a[i] represent length of ith candle. There is a tradition according to which you celebrate by lighting a candle every night. The candles are lit such that there are k candles lit on the… Read More »
Problem: Given a positive integer N, arrange the integers 1 to N such the position of the average of two numbers (if present) falls outside the two numbers. For example, for a[i] and a[j], if b = (a[i] + a[j])/2, then if a[k] = b, k < i or k > j. Hint :- If the average… Read More »
These numbers are catalan numbers: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452 F(0) = 1 F(1) = 1 F(2) = 2 F(3) = 5 F(4) = 14 …. The formula of catalan could be: Some cases… Read More »
Divide number and return result in form of a string. e.g 100/3 result should be 33.(3) Here 3 is in brackets because it gets repeated continuously and 5/10 should be 0.5. The essence is to use hashmap to restore the remainder. Once a certain remainder was obtained for 2nd time, we found the recycles. public… Read More »