Algorithms on numbers

AAA_Number_Utils.txt

Algorithms on numbers

ClockAngleJTests.java

package com.blogspot.groglogs.test.numberutils;

import static org.junit.Assert.assertEquals;

import com.blogspot.groglogs.numberutils.NumberUtils;
import org.junit.Test;

public class ClockAngleJTests {

	private static double EPSILON = 0.00001;

	int hours, minutes;
	float angle;

	@Test
	public void badTime(){
		hours = -1;
		minutes = 10;
		angle = -1;
		assertEquals("-1:10", angle, NumberUtils.clockAngle(hours, minutes), EPSILON);

		hours = 1;
		minutes = -10;
		angle = -1;
		assertEquals("1:-10", angle, NumberUtils.clockAngle(hours, minutes), EPSILON);
	}

	@Test
	public void overlap(){
		hours = 12;
		minutes = 0;
		angle = 0;
		assertEquals("12:0", angle, NumberUtils.clockAngle(hours, minutes), EPSILON);

		hours = 9;
		minutes = 49;
		angle = 0.5f;//lazy, we do not have seconds so the 0 overlap is exactly at 9:49:5
		assertEquals("9:49", angle, NumberUtils.clockAngle(hours, minutes), EPSILON);

		hours = 21;
		minutes = 49;
		angle = 0.5f;//lazy, we do not have seconds so the 0 overlap is exactly at 21:49:5
		assertEquals("21:49", angle, NumberUtils.clockAngle(hours, minutes), EPSILON);
	}

	@Test
	public void sample(){
		hours = 2;
		minutes = 20;
		angle = 50;
		assertEquals("2:20", angle, NumberUtils.clockAngle(hours, minutes), EPSILON);

		hours = 14;
		minutes = 20;
		angle = 50;
		assertEquals("14:20", angle, NumberUtils.clockAngle(hours, minutes), EPSILON);
	}
}

FactorialTrailingZeroesJTests.java

package com.blogspot.groglogs.test.numberutils;

import static org.junit.Assert.assertEquals;

import com.blogspot.groglogs.numberutils.NumberUtils;
import org.junit.Test;

public class FactorialTrailingZeroesJTests {

	int n, expected;

	@Test
	public void badNumber(){
		n = 0;
		expected = 0;
		assertEquals("0", expected, NumberUtils.factorialTrailingZeroes(n));

		n = -10;
		expected = 0;
		assertEquals("-10", expected, NumberUtils.factorialTrailingZeroes(n));
	}

	@Test
	public void noZeroes(){
		n = 2;
		expected = 0;
		assertEquals("2", expected, NumberUtils.factorialTrailingZeroes(n));

		n = 4;
		expected = 0;
		assertEquals("4", expected, NumberUtils.factorialTrailingZeroes(n));
	}

	@Test
	public void zeroes(){
		n = 5;
		expected = 1;
		assertEquals("5", expected, NumberUtils.factorialTrailingZeroes(n));

		n = 10;
		expected = 2;
		assertEquals("10", expected, NumberUtils.factorialTrailingZeroes(n));

		n = 100;
		expected = 24;
		assertEquals("100", expected, NumberUtils.factorialTrailingZeroes(n));
	}
}

FindMissingNumberJTests.java

package com.blogspot.groglogs.test.numberutils;

import com.blogspot.groglogs.numberutils.NumberUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class FindMissingNumberJTests {
    int[] numbers;
    int expected;

    @Test
    public void nullArray(){
        numbers = null;
        expected = -1;
        assertEquals("null", expected, NumberUtils.findMissingNumber(numbers));
    }

    @Test
    public void missingZero(){
        numbers = new int[]{1};
        expected = 0;
        assertEquals("1", expected, NumberUtils.findMissingNumber(numbers));

        numbers = new int[]{1,2};
        expected = 0;
        assertEquals("1,2", expected, NumberUtils.findMissingNumber(numbers));

        numbers = new int[]{2,1};
        expected = 0;
        assertEquals("2,1", expected, NumberUtils.findMissingNumber(numbers));
    }

    @Test
    public void missingOne(){
        numbers = new int[]{0};
        expected = 1;
        assertEquals("0", expected, NumberUtils.findMissingNumber(numbers));

        numbers = new int[]{0,2};
        expected = 1;
        assertEquals("0,2", expected, NumberUtils.findMissingNumber(numbers));

        numbers = new int[]{2,0};
        expected = 1;
        assertEquals("2,0", expected, NumberUtils.findMissingNumber(numbers));
    }

    @Test
    public void missingTwo(){
        numbers = new int[]{0,1};
        expected = 2;
        assertEquals("0,1", expected, NumberUtils.findMissingNumber(numbers));

        numbers = new int[]{1,0};
        expected = 2;
        assertEquals("1,0", expected, NumberUtils.findMissingNumber(numbers));

        numbers = new int[]{0,1,3};
        expected = 2;
        assertEquals("0,1,3", expected, NumberUtils.findMissingNumber(numbers));
    }
}

GenerateKth357JTests.java

package com.blogspot.groglogs.test.numberutils;

import static org.junit.Assert.assertEquals;

import com.blogspot.groglogs.numberutils.NumberUtils;
import org.junit.Test;

public class GenerateKth357JTests {

	int k;
	int[] expected = {1, 3, 5, 7, 9, 15, 21, 25, 27, 35, 45, 49, 63, 75, 81};

	@Test
	public void badK(){
		k = -1;
		assertEquals("negative", 0, NumberUtils.generateKth357(k));
	}

	@Test
	public void sample(){
		for(int i = 0; i < expected.length; i++){
			assertEquals("iteration: " + (i + 1), expected[i], NumberUtils.generateKth357(i + 1));
		}
	}
}

MakeBiggestNumberJTests.java

package com.blogspot.groglogs.test.numberutils;

import com.blogspot.groglogs.numberutils.NumberUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class MakeBiggestNumberJTests {
    String[] numbers;
    String expected;

    @Test
    public void nullEmpty(){
        numbers = null;
        expected = "";
        assertEquals("null", expected, NumberUtils.makeBiggestNumber(numbers));

        numbers = new String[]{};
        expected = "";
        assertEquals("empty", expected, NumberUtils.makeBiggestNumber(numbers));
    }

    @Test
    public void same(){
        numbers = new String[]{"1", "1", "1", "1", "1"};
        expected = "11111";
        assertEquals("1,1,1,1,1", expected, NumberUtils.makeBiggestNumber(numbers));

        numbers = new String[]{"1", "11", "1", "11", "1"};
        expected = "1111111";
        assertEquals("1,11,1,11,1", expected, NumberUtils.makeBiggestNumber(numbers));
    }

    @Test
    public void increasing(){
        numbers = new String[]{"1", "2", "3", "4", "5"};
        expected = "54321";
        assertEquals("1,2,3,4,5", expected, NumberUtils.makeBiggestNumber(numbers));

        numbers = new String[]{"1", "10", "11", "12", "13"};
        expected = "131211110";
        assertEquals("1,10,11,12,13", expected, NumberUtils.makeBiggestNumber(numbers));
    }

    @Test
    public void decreasing(){
        numbers = new String[]{"5", "4", "3", "2", "1"};
        expected = "54321";
        assertEquals("5,4,3,2,1", expected, NumberUtils.makeBiggestNumber(numbers));

        numbers = new String[]{"13", "12", "11", "10", "1"};
        expected = "131211110";
        assertEquals("13,12,11,10,1", expected, NumberUtils.makeBiggestNumber(numbers));
    }

    @Test
    public void biggestIsNotAlwaysFirst(){
        numbers = new String[]{"500", "60"};
        expected = "60500";
        assertEquals("500,60", expected, NumberUtils.makeBiggestNumber(numbers));

        numbers = new String[]{"9", "98"};
        expected = "998";
        assertEquals("9,98", expected, NumberUtils.makeBiggestNumber(numbers));

        numbers = new String[]{"4", "45"};
        expected = "454";
        assertEquals("4,45", expected, NumberUtils.makeBiggestNumber(numbers));
    }

    @Test
    public void sample(){
        numbers = new String[]{"17", "7", "2", "45", "72"};
        expected = "77245217";
        assertEquals("17,7,2,45,72", expected, NumberUtils.makeBiggestNumber(numbers));
    }
}

NRootJTests.java

package com.blogspot.groglogs.test.numberutils;

import com.blogspot.groglogs.numberutils.NumberUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class NRootJTests {

    double n, expected, epsilon = 0.001;
    int root;

    @Test
    public void badInput() {
        n = -1;
        root = 2;
        expected = -1;
        assertEquals("-1,2", expected, NumberUtils.nRoot(n, root), epsilon);

        n = 0;
        root = 2;
        expected = -1;
        assertEquals("0,2", expected, NumberUtils.nRoot(n, root), epsilon);

        n = 3;
        root = 0;
        expected = -1;
        assertEquals("3,0", expected, NumberUtils.nRoot(n, root), epsilon);
    }

    @Test
    public void oneRoot() {
        n = 3;
        root = 1;
        expected = n;
        assertEquals("3,1", expected, NumberUtils.nRoot(n, root), epsilon);
    }

    @Test
    public void perfectSquares() {
        n = 9;
        root = 2;
        expected = 3;
        assertEquals("9,2", expected, NumberUtils.nRoot(n, root), epsilon);

        n = 4;
        root = 2;
        expected = 2;
        assertEquals("4,2", expected, NumberUtils.nRoot(n, root), epsilon);

        n = 16;
        root = 2;
        expected = 4;
        assertEquals("16,2", expected, NumberUtils.nRoot(n, root), epsilon);
    }

    @Test
    public void perfectRoot() {
        n = 27;
        root = 3;
        expected = 3;
        assertEquals("27,3", expected, NumberUtils.nRoot(n, root), epsilon);

        n = 16;
        root = 4;
        expected = 2;
        assertEquals("16,4", expected, NumberUtils.nRoot(n, root), epsilon);

        n = 243;
        root = 5;
        expected = 3;
        assertEquals("243,5", expected, NumberUtils.nRoot(n, root), epsilon);
    }

    @Test
    public void sample() {
        n = 3;
        root = 2;
        expected = 1.732;
        assertEquals("3,2", expected, NumberUtils.nRoot(n, root), epsilon);

        n = 5;
        root = 3;
        expected = 1.709;
        assertEquals("5,3", expected, NumberUtils.nRoot(n, root), epsilon);
    }
}

NumberUtils.java

package com.blogspot.groglogs.numberutils;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class NumberUtils {

    private static void swap(int[] a, int i, int j){
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    /**
     * Given a number, find the next bigger number that uses the same digits.
     * @param num the given number.
     * @return the next bigger number that uses the same digits.
     */
    public static int smallestBiggerNumWithSameDigits(int num){
        if(num < 0){
            return -1;
        }

        /*
        Need to convert number to array for digit manipulation, convert it first to string and then to array.
        Then, we need to identify (if any) a digit that can be swapped in another place. If it exists, it will be
        the first digit from the right which is smaller than the next digit.

        Example: 9876
        has no valid digit since that is already the biggest number that can be made with those digits: all are in
        decreasing order

        Example: 6789
        the first digit smaller than the next from the right is 8, we can use it to make 6798 which is the next
        bigger number than 6789

        But simply swapping is not enough, example: 8276, a swap would give 8672 which is not the next, that would
        be 8627.
        We notice that after the swap, the rest of the digits on the right of the swapped one are sorted in
        increasing order.

        If we do that, we have our answer, this reordering can be done in linear time since in the first portion
        we stop as soon as we find an element that breaks the increasing sequence right to left.
         */

        //convert number to array
        String numString = Integer.toString(num);

        int[] number = new int[numString.length()];
        for(int i = 0; i < numString.length(); i++){
            number[i] = numString.charAt(i) - '0';
        }

        //find if any, a digit to swap
        int swapIdx = number.length - 1;

        for(int i = number.length - 1; i > 0; i--){
            //swap candidate is the first digit smaller than the next on the right
            if(number[i] > number[i - 1]){
                swapIdx = i - 1;
                break;
            }
        }

        //find if any, the smallest digit larger than the one to swap on its right side
        int smallestLargerIdx = number.length - 1;

        for(int i = number.length - 1; i > swapIdx; i--){
            //swap candidate is the first number bigger than our swap digit
            if(number[i] > number[swapIdx]){
                smallestLargerIdx = i;
                break;
            }
        }

        //swap the digits
        swap(number, swapIdx, smallestLargerIdx);

        //reorder the rest of the digits on the right side of the swapped one in increasing order
        //since they were already in decreasing order, we just swap them in pairs
        for(int i = swapIdx + 1, j = number.length - 1; i < j; i++, j--){
            swap(number, i, j);
        }

        //rebuild our number from the array
        int res = 0;
        for(int i = number.length - 1, j = 0; i >= 0; i--, j++){
            res += number[i] * (Math.pow(10, j));
        }

        return res;
    }

    /**
     * Calculate the nth root of the given number.
     * @param n the number.
     * @param root the nth root to calculate.
     * @return the nth root of the given number.
     */
    public static double nRoot(double n, int root){
        //consider only real values
        if(n <= 0 || root <= 0){
            return -1;
        }

        //1st root is always the number
        if(root == 1){
            return n;
        }

        //precision for our approximation
        final double epsilon = 0.001;

        /*
        Use binary search in range 0..N to calculate nth power of mid and see how far off we are from N
        mid would be the nth root if mid^root = N with at most epsilon difference
        If mid^root is bigger than N, we search on left side, otherwise on right side
        We repeat until we have reached the desired approximation
         */
        double floor = 0;
        double ceil = n;
        double mid = -1;

        while(floor < ceil){
            //mid is our nth root
            mid = floor + (ceil - floor) / 2;

            //multiply mid with itself root times to calculate mid^root
            double r = mid;
            //start from 1 up to root, so we multiply root - 1 times which is the exact number of multiplications we want
            //eg square root (2) is one multiplication only
            for(int i = 1; i < root; i++){
                //multiply with ITSELF, NOT r!! we want mid*mid* ... root times
                r *= mid;
            }

            //check if our root approximation is at most epsilon different from actual value (N)
            //if yes, we have our answer
            if(Math.abs(n - r) <= epsilon){
                break;
            }

            //if we overshot or undershot adjust bound correctly
            //set them EQUAL to mid since we're dealing with doubles, any fluctuation in mid + or - something might be incorrect
            if(r > n){
                ceil = mid;
            }
            else{
                floor = mid;
            }
        }

        //when get to this point, mid was the nth root with precision epsilon
        return mid;
    }

    /**
     * Given an array of unique integers in range 0..N with only one missing value, find the missing value.
     * @param numbers the input numbers.
     * @return the missing value.
     */
    public static int findMissingNumber(int... numbers){
        if(numbers == null){
            return -1;
        }

        int n = numbers.length;

        //if we had all numbers in range 0..N this is the total value we would have
        int expected = n * (n + 1) / 2;

        //sum up all the values in the array
        int tot = 0;

        for(int i = 0; i < numbers.length; i++){
            tot += numbers[i];
        }

        //our answer is expected - sum
        return expected - tot;
    }

    /**
     * Given an array of integers, return the biggest number that can be made by repositioning the individual numbers.
     * @param numbers the given numbers.
     * @return the biggest number that can be made using all individual numbers.
     */
    public static String makeBiggestNumber(String... numbers){
        if(numbers == null || numbers.length == 0){
            return "";
        }

        StringBuilder sb = new StringBuilder();

        /*
        We need to sort our input in a way that gives us the biggest choices first, however we can't simply compare values
        as for example:
        500,60
        500 > 60 but the biggest number is 60500 and not 50060
        Also cannot go with single digit comparison as for example:
        9,98 we want 998
        but:
        4,45 we want 454

        So by observing how we would manually arrange the numbers, we see the solution: pick the order that gives the
        biggest resulting number when choosing only those two numbers.
        We combine the strings into a number AB and BA, then pick the biggest of the two to determine the order of A and B
         */
        Arrays.sort(numbers, (n1, n2) -> -Integer.compare(Integer.parseInt(n1 + n2), Integer.parseInt(n2 + n1)));

        for(String s : numbers){
            sb.append(s);
        }

        return sb.toString();
    }

    /**
     * Return the kth number generated by using only the primes 3,5,7.
     * Formula is 3^x * 5^y * 7^z.
     * @param k the desired iteration.
     * @return the kth number generated by using only the primes 3,5,7.
     */
    public static int generateKth357(int k){
        if(k < 0){
            return 0;
        }

        /*
        Maintain 3 queues: generated by 3, 5 and 7
        Each round pick the minimum from the top of the queues and multiply by 3,5,7 and push back to the corresponding queue
        If the min is more than the top of the queue, skip that queue
        When we reach the kth iteration, stop and return min as the result.
         */
        int out = 0;

        Queue<Integer> threes = new LinkedList<>();
        Queue<Integer> fives = new LinkedList<>();
        Queue<Integer> sevens = new LinkedList<>();

        for(int curr = 0; curr < k; curr++){
            //initially queues are empty so we must fake having pushed the 1 ourselves
            int min3 = threes.isEmpty() ? 1 : threes.peek();
            int min5 = fives.isEmpty() ? 1 : fives.peek();
            int min7 = sevens.isEmpty() ? 1 : sevens.peek();

            int min = Math.min(min3, Math.min(min5, min7));

            //0 based so kth iteration is k-1
            if(curr == k - 1){
                out = min;
                break;
            }

            if(min == min3){
                //threes queue could be empty at the very beginning, avoid NPE
                threes.add((threes.isEmpty() ? 1 : threes.poll()) * 3);
                fives.add(min * 5);
                sevens.add(min * 7);
            }
            else if(min == min5){
                fives.add(fives.poll() * 5);
                sevens.add(min * 7);
            }
            else{
                sevens.add(sevens.poll() * 7);
            }
        }

        return out;
    }

    /**
     * Given a number n, return the amount of trailing zeroes in its factorial.
     * @param n the given number
     * @return the amount of trailing zeroes in n!
     */
    public static int factorialTrailingZeroes(int n){
        if(n <= 0){
            return 0;
        }

        /*
        The only way to have a zero in output is to have a pair 5,2 to obtain a 10 multiplication factor
        We can simply count the amount of such pairs contained in the factorial of the given number.

        Since 2 is smaller than 5 we only consider the amount of 5s appearing in the multiplication chain
        as for sure the amount of 2s will be greater than the amount of 5s.

        example:
        26! has: 25 (5*5), 20(5*4), 15(5*3), 10(5*2), 5(5*1) as terms containing a 5, for a total of 6 5s
        Each of these will have a matching 2 to complete the pair, therefore there will be 6 trailing zeros in the output

        We keep dividing the given N for the current power of 5 until we exceed the number. Each division will provide the amount
        of 5s in the multiplication chain for a portion of the factors

        eg: 10!
        the chain contains 10(5*2) and 5(5*1) for a total of two 5s, 10/5^1 = 2
        5^2 is bigger than 10, so no more terms including a 5 would appear in the chain
         */

        int count = 0;
        int num = n;

        while(num >= 5){
            num /= 5;
            count += num;
        }

        return count;
    }

    /**
     * Given the current hours and minutes, calculate the smallest angle between the two clock hands.
     * @param hours
     * @param minutes
     * @return
     */
    public static float clockAngle(int hours, int minutes){
        if(hours < 0 || hours > 24 || minutes < 0 || minutes > 60){
            return -1;
        }

        /*
        The hour hand makes a 360 degree turn every 12 hours or 12*60 = 720 minutes
        therefore each minute the hand moves 360/720 = 0.5 degrees

        The minute hand makes a 360 degree turn every hour or 60 minutes
        therefore each minute the hand moves 360/60 = 6 degrees

        Setting 12 as the 0 position, to calculate the angle of each hand we can:
        hours = 0.5 * current minutes for that hour (60 * hours + minutes)
        minutes = 6 * minutes

        We now have the position of both hand with respect to the 12 o'clock, the angle between them will simply be the difference
        between the two positions (absolute value!)

        If the difference is more than 180 degrees, the angle is a reflex angle (>180 and <360) and since we want the smallest
        angle between the hands, we take its complement by subtracting it from 360
         */
        float angle;

        float hourAngle = 0.5f * (60 * hours + minutes);
        float minuteAngle = 6 * minutes;

        angle = Math.abs(hourAngle - minuteAngle);

        if(angle > 180){
            angle = Math.abs(360 - angle);
        }

        return angle;
    }
}

SmallestBiggerNumWithSameDigitsJTests.java

package com.blogspot.groglogs.test.numberutils;

import com.blogspot.groglogs.numberutils.NumberUtils;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class SmallestBiggerNumWithSameDigitsJTests {

    int num, expected;

    @Test
    public void negative() {
        num = -1;
        expected = -1;
        assertEquals("-1", expected, NumberUtils.smallestBiggerNumWithSameDigits(num));
    }

    @Test
    public void oneDigit() {
        num = 0;
        expected = 0;
        assertEquals("0", expected, NumberUtils.smallestBiggerNumWithSameDigits(num));

        num = 9;
        expected = 9;
        assertEquals("9", expected, NumberUtils.smallestBiggerNumWithSameDigits(num));
    }

    @Test
    public void allSame() {
        num = 555;
        expected = 555;
        assertEquals("555", expected, NumberUtils.smallestBiggerNumWithSameDigits(num));
    }

    @Test
    public void decreasing() {
        num = 9876;
        expected = 9876;
        assertEquals("9876", expected, NumberUtils.smallestBiggerNumWithSameDigits(num));
    }

    @Test
    public void increasing() {
        num = 6789;
        expected = 6798;
        assertEquals("6789", expected, NumberUtils.smallestBiggerNumWithSameDigits(num));
    }

    @Test
    public void sample() {
        num = 38276;
        expected = 38627;
        assertEquals("38276", expected, NumberUtils.smallestBiggerNumWithSameDigits(num));

        num = 34722641;
        expected = 34724126;
        assertEquals("34722641", expected, NumberUtils.smallestBiggerNumWithSameDigits(num));
    }
}

Full description at:

• https://groglogs.blogspot.com/2021/10/java-calculate-angle-between-clock-hands.html
• https://groglogs.blogspot.com/2021/10/java-number-of-trailing-zeroes-in.html
• https://groglogs.blogspot.com/2021/10/java-generate-k-th-number-made-only-of.html
• https://groglogs.blogspot.com/2021/09/java-make-biggest-number-from-list-of.html
• https://groglogs.blogspot.com/2021/07/java-find-missing-integer-in-array-of.html
• https://groglogs.blogspot.com/2021/07/java-calculate-nth-root.html
• https://groglogs.blogspot.com/2021/07/java-find-next-bigger-number-using-same.html