|
BiggestFromArray |
Tests |
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int makeBiggestNumberFromIntArray(int[] a) String[] sa
= Arrays.stream(a).mapToObj(String::valueOf).toArray(String[]::new);> Arrays.sort(sa, (s1,
s2)
-
{
> String leftRight = s1 + s2;> String rightLeft = s2 + s1;> return
rightLeft.compareTo(leftRight);> });
String
s = Arrays.stream(sa).collect(Collectors.joining());> return Integer.valueOf(s);>}
|
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass() boolean
check = makeBiggestNumberFromIntArray(new int[] {7, 9, 91, 73}) == 991773;pre
data-role="codeBlock"
data-info="js"
class="language-javascript"> if(!check)
{
return false;> }> return true; }
|
ClockAngle
Tests
// The minute hand moves 360 degrees in 60 minutes(or 6 degree in one minute)>// The hour hand moves 360 degrees in 12 hours (720 mins), or 0.5 degrees per minute.// In h hours and m minutes:>// the hour hand will move (h * 60 + m) * 0.5 degrees// the minute hand will move (h * 60 + m) * 6 degrees// Assume 12:00 as the reference point// In h hours and m minutes:// the hour hand will move (h * 60 + m) * 0.5 degrees// the minute hand will move (h * 60 + m) * 6 degrees, or 6 * m// For them to superimpose, both angles should be equal>// 0.5 * (60H + M) = 6*M>// 60H + M = 12M >// 60H = 11M// M = 5.45H// Thus, as H varies from 1 to 11, hands will overlap 11 times in 12 hours// H M// ----->// 1 1:05.45>// 2 2:10.90>// 3 3:16.36> if(hour 0 || hour 12 || min 0 || min 60)> {> return -1;> }if(hour == 12){> hour = 0;> }if(min == 60){> min = 0;> }int hourAngle = (int)(0.5 * (hour * 60 + min));> int minAngle = (int)(6 * min);> int angle = Math.abs(hourAngle - minAngle);> angle = Math.min(360 - angle, angle);> return angle;>}boolean check = angle(1, 5.45) == 0;if(!check){> return false;> }check = angle(2, 10.9) == 0;if(!check)> {> return false;> }return true;}
EggDrop
Tests
// 1st Egg If first egg breaks - 2nd egg Drops> // --------------------------------------------------------------> // 14 1-2-3-4-5-6-7-8-9-10-11-12-13 1+13=14> // 27 15-16-17-18-19-20-21-22-23-24-25-26 2+2=14> // 39> // 50// 60// 69> // 77> // 84> // 90 9+5=14> // 95 10+4=14> // 99 11+3=14> // 102 12+2=14> // 104 13+1=14> // 105 14+0=14> //// We can see how this becomes the consecutive range sum problem where n = 14pre data-role="codeBlock" data-info="js" class="language-javascript"> // Thus,> // n(n + 1)/2 = 14*15/2 = 105> // n*n + n - 210 = 0 > // a = 1, b = 1, c = -210> // Using quadratic equation:> // x = (-b +/- SQRT(b^2 - 4ac)) / 2a> // n = (-1 + Sqrt(1 + 840)) / 2 = 14>int a = 1, b = 1, c = -floor * 2;double sqrt = Math.sqrt(Math.pow(b, 2) - 4 * a * c);int root1 = (int)(-b + sqrt) / (2 * a);int root2 = (int)(-b - sqrt) / (2 * a);return root1 0 ? root1 : root2;}boolean check = drops(105) == 14;if(!check){> return false;> }return true;}
ExcelColumn
Tests
StringBuilder sb = new StringBuilder();while(n 0){> int rem = n % 26;> // if rem == 0, the 'Z' must be there> if(rem == 0)> {> sb.append("Z");> n = n / 26 - 1;> }else{> sb.append((char) (rem - 1 + 'A'));> n /= 26;> }}return sb.reverse().toString();>}boolean check = numberToExcelColumn(26).equals("Z");> if(!check){return false;> }> check = numberToExcelColumn(52).equals("AZ");> if(!check)> {return false;}> return true;>}
FactorialTrailingZeros
if(n 0){> return -1;> }int count = 0;while(n 0)> {> count += n / 5;> n /= 5;> }return count;}
FromArray
Tests
val = val * 10 + v;}> return val;>}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int fromArrayOfOneDigitIntsRightToLeft(int [] a)> int val = 0, pow = 0;> for(int i = a.length - 1; i = 0; --i)> {val += Math.pow(10, pow++) * a[i];}> return val;>}boolean check = fromArrayOfOneDigitIntsLeftToRight(new int[] {3, 4, 5, 6}) == 3456;> if(!check) > {return false;}> check = fromArrayOfOneDigitIntsRightToLeft(new int[] {3, 4, 5, 6}) == 3456;if(!check){> return false;> }return true;}
GasStations
Tests
// Input is provided in a 2D array, for example:// {4, 6},// {6, 5},>// {1, 3},>// {7, 4},>// Where the first value is the amount of petrol and the next value is the distance to the next station.// To make it easier, we convert each coordinate to a Unit {petrol, distance}>private static class Unit{> int petrol;> int distance;> Unit(int petrol, int distance) > {> this.petrol = petrol;> this.distance = distance;> }}> static int startingStation(int[][] data)> {> ListUnit units = Arrays.stream(data).map((int[] a) - new Unit(a[0], a[1])).collect(Collectors.toList());> {> Unit unit = units.get(i);> if(unit.distance unit.petrol + supply)> {> continue;> } >// Check if we can visit all stations from "good" starting point> int j = 0; > for(; j units.size(); ++j) > {> Unit currentUnit = units.get((i + j) % units.size());> if(currentUnit.distance currentUnit.petrol + supply){break;> }> supply += currentUnit.petrol - currentUnit.distance; > }> > // if we could visit all stations> if(j == units.size())> {> return i;> }> // Try competing tour from the next station> supply = 0;> }return -1;}>}boolean check = startingStation(new int[][] {{4, 6}, {6, 5}, {1, 3}, {7, 4}}) == 3;> if(!check) > {return false;}> return true;>}
Gcd
Tests
int gcd = Math.min(Math.abs(a), Math.abs(b));while(gcd 0){> if(a % gcd == 0 && b % gcd == 0){> break;> }gcd--;}> return gcd;>}boolean check = findGcd(8, 36) == 4;if(!check){> return false;> }return true;}
GcdFromArray
Tests
int minGcd = Integer.MAX_VALUE;for(int i = 0; i a.length - 1; ++i){> for(int j = i + 1; j a.length; ++j){> minGcd = Math.min(minGcd, gcd(a[i], a[j]));> } > }return minGcd;}boolean check = gcdFromArray(new int[] {12, 36, 24, 8}) == 4;> if(!check){return false;> }> return true;}
IsPalindrome
Tests
int original = n;int reversed = 0;> while(n 0)> {> reversed = reversed * 10 + n % 10; > n /= 10; > }return reversed == original;}boolean check = isPalindrome(123321);if(!check){> return false;> }check = isPalindrome(12345);if(check)> {> return false;> }return true;}
Josephus
Tests
ListInteger list = IntStream.rangeClosed(1, n).boxed().collect(Collectors.toList());> int i = -1;> while (list.size() 1)> {list.remove((i + k) % list.size());i = (i + k) % (list.size() + 1) - 1;}return list.get(0);>}boolean check = josephus(5, 2) == 3;if(!check){> return false;> }return true;}
JourneyStartAmount
Tests
// A traveler visits multiple cities.// He can work daily and make some money. He also spends some money on each day.> // An array is given depicting his daily savings (earnings – expenses) over the course of his journey.// How much minimum money he should start with in order to have at least some saving ( 0) at the end of each day.> // Examples: arr[] = { 10, -5, 7, -8, 5, -9 }// He had to have 10 before the start of the last day in order to have 1 left after spending 9> // At the end of the journey he has $1 left. > // Thus:> // 1 - (-9) = 10> // 10 - 5 = 5> // 5 - (-8) = 13> // 13 - 7 = 6> // 6 - (-5) = 11> // 11 - 10 = 1> int sum = 1; > for(int i = a.length - 1; i = 0; i--)> {sum -= a[i];}> return sum;>}boolean check = amountAtStartOfJourney(new int[] {10, -5, 7, -8, 5, -9}) == 1;> if(!check){return false;> }> return true;}
MinValueFromSequence
Tests
// Given a pattern containing only I’s and D’s. I for increasing and D for decreasing.>// Devise an algorithm to print the minimum number following that pattern.// Digits from 1-9 can’t repeat.>// Examples:>// Input: D Output: 21>// Input: I Output: 12>// Input: DD Output: 321>// Input: II Output: 123>// Input: DIDI Output: 21435>// Input: IIDDD Output: 126543>// Input: DDIDDIID Output: 321654798 >//>// Number of digits in output is one more than number of characters in input.>// Note that the first character of input corresponds to two digits in output.// The tricky part occurs when 'D' is encountered at index other than 0.>// In such a case we have to track the nearest 'I' to the left of 'D'>// and increment each number in the output vector by 1 in between ‘I’ and ‘D’.ListInteger result = new ArrayList();int nextNumber = 3;int posOfLastI = 0;> if(s.charAt(0) == 'I')> {> result.add(1);> result.add(2);> }else{> result.add(2);> result.add(1);> }for(int i = 1; i s.length(); ++i){> if(s.charAt(i) == 'I')> {> result.add(nextNumber++); > posOfLastI = i + 1;> }else{> result.add(result.get(i));> for(int j = posOfLastI; j = i; ++j) > { > result.set(j, result.get(j) + 1);> } > nextNumber++;> }}int num = 0;> for(int i : result)> {> num = num * 10 + i;> }return num;}boolean check = compute("D") == 21;if(!check){> return false;> }> check = compute("I") == 12;> if(!check){return false;> }> check = compute("IIDDD") == 126543;> if(!check)> {return false;}> return true;>}
NumberToWords
Tests
static String[] numNames = {"","one","two",> "three",> "four", > "five",> "six",> "seven",> "eight",> "nine",> "ten",> "eleven",> "twelve",> "thirteen",> "fourteen",> "fifteen",> "sixteen",> "seventeen",> "eighteen",> "nineteen"> }; > static String[] tenNames = { > "",> "ten",> "twenty",> "thirty",> "forty",> "fifty",> "sixty",> "seventy",> "eighty",> "ninety",> };static String[] bigNumNames = {"","thousand","million","billion","trillion","quadrillion","quintillion"};> > static String convert(long num) > {if(num == 0){> return "zero";> }>String prefix = "";if(num 0){> prefix = "negative";> num = -num;pre data-role="codeBlock" data-info="js" class="language-javascript"> }>String current = "";int bigNumPlace = 0;> do> {> long n = num % 1000;> if(n != 0) > {> String s = convertLessThan1000(n);> current = s + bigNumNames[bigNumPlace++] + current; > }> num /= 1000;> } while (num 0);> return prefix + current;> }> {> return convertLessThan100(n);> }private static String convertLessThan1000(long n){> if(n 100)> return numNames[(int)hundreds] + "hundred" + convertLessThan100(rem);> }private static String convertLessThan100(long n){> if(n 20)> return tenNames[(int)tens] + convertLessThan20(rem);boolean check = convert(-12_345_678_901L).equals("negativetwelvebillionthreehundredfortyfivemillionsixhundredseventyeightthousandninehundredone");if(!check)> {> return false;> }return true;}
PowerOf10
Tests
for(int i = 1; i = n; i *= 10){> if(i == n)> {> return true;> }if(i Integer.MAX_VALUE / 10){return false;> }> }return false;}boolean check = isPowerOf10(1) &&> isPowerOf10(10) && > isPowerOf10(100) &&> isPowerOf10(1000) &&> isPowerOf10(1000000);> if(!check)> {> return false;> }return true;}
PrimeFactorization
Tests
if(n 2){> return new int[0];> }ListInteger factors = new ArrayList();> for(int i = 2; i = n; ++i)> {while(n % i == 0){> factors.add(i);> n /= i;> }> }return factors.stream().mapToInt(x - x).toArray();>}boolean check = Arrays.equals(new int[] {2, 2, 2, 2}, primeFactorsOfProduct(16));pre data-role="codeBlock" data-info="js" class="language-javascript"> if(!check){return false;> }> check = Arrays.equals(new int[] {2, 5}, primeFactorsOfProduct(10));> if(!check)> {> return false;> }check = Arrays.equals(new int[] {2, 2, 3}, primeFactorsOfProduct(12));> if(!check){return false;> }> return true;}
Primes
Tests
// 1. 2 is the first prime number// 2. use = when comparing Sqrt. Consider number 9if(n 2){> return false;> }> if(n == 2){return true;> }> if(n % 2 == 0)> {return false;}> for(int i = 3; i = Math.sqrt(n); i += 2){> if(n % i == 0)> {> return false;> }}return true;>}>> if(n 1)> {return new int[0];}> int[] primes = new int[n];> primes[0] = 2;> int idx = 1;> int candidate = 3;> while(idx n) > {boolean isPrime = true;for(int i = 0; primes[i] = Math.sqrt(candidate); ++i)> {> if(candidate % primes[i] == 0) > {> isPrime = false;> break;> }> }if(isPrime){> primes[idx++] = candidate;> }> candidate += 2;> }return primes;}boolean check = isPrime(71);if(!check)> {> return false;> }check = isPrime(81);if(check)> {> return false;> }check = Arrays.equals(new int[] {2, 3, 5, 7, 11, 13, 17}, genPrimes(7));> if(!check){return false;> }> return true;}
Random7
Tests
while(true){> int mod2 = rand5();> if(mod2 != 4)> { > mod2 %= 2;> int r1 = rand5() * 2;> int n = r1 + mod2;> if(n 7)> {return n;}> }> }}> >private static int rand5()> return (int)(Math.random() * 5);>}System.out.println(rand7UsingRand5());return true;}
RomanNumeral
Tests
String[] romSym = {"M","CM","D","CD", "C","XC","L","XL","X","IX","V","IV","I"};int[] decimals = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};StringBuilder sb = new StringBuilder();for(int i = 0; i decimals.length; ++i)> {while(n = decimals[i]){> sb.append(romSym[i]);> n -= decimals[i];> } > if(n == 0)> { > break;> }}return sb.toString();>}boolean check = romanNumeral(4998).equals("MMMMCMXCVIII");> if(!check){return false;> }> return true;}
SquareRoot
Tests
if(n 2){> return n;> }int low = 1, high = n / 2;while(low = high){> int mid = (low + high) / 2;> int sqr = mid * mid;> if(sqr == n) > { > return mid;> }else if(sqr n){> low = mid + 1;> }> else> { > high = mid - 1;> }}return -1;>}boolean check = squareRoot(81) == 9;if(!check){> return false;> }return true;}
StairCaseHeight
Tests
// Given N blocks, how many steps can be made.// 1 block - 1 step// 2 blocks - 1 step// 3 blocks - 2 steps>// ...>// Note that this is a consecutive sum problem: N = n(n+1) / 2>// n*n + n = 2N>// n*n + n - 2N = 0>// Where:// a = 1, b = 1, c = -(2 * N)// a(x*x) + bx + c = 0if(blocks 2)> {> return blocks;> }int a = 1, b = 1, c = -blocks * 2;double sqrt = Math.sqrt(Math.pow(b, 2) - 4 * a * c);int root1 = (int)(-b + sqrt) / (2 * a);int root2 = (int)(-b - sqrt) / (2 * a);return root1 0 ? root1 : root2;}boolean check = height(55) == 10;if(!check){> return false;> }return true;}
StringToNumber
Tests
char[] a = s.toCharArray();int n = 0;> for(char c : a)> {> n = n * 10 + c - '0';> }return n;}boolean check = 12345 == numericStringToNum("12345");> if(!check){return false;> }> return true;}
ToBinary
Tests
StringBuilder sb = new StringBuilder();while(n 0){> sb.append(n % 2);> n /= 2;> }> return sb.reverse().toString(); >}boolean check = toBinary(14).equals("1110");> if(!check){return false;> }> return true;}