Discussion on: Daily Challenge #111 - 99 Bottles of Beer

[Vitaliy Kononenko]

Here is O(log(n)) solution using Kotlin. We use the arithmetic progression formula to calculate the sum from 1 to n without a loop with O(1) complexity. And after we use the binary search to find the number of iterations needed with O(log(n)) complexity. This will work for very large values of n, although I do not think anybody will have such a big number of beers on the wall:)

Result for n=Long.MAX_VALUE=9223372036854775807 is (4294967296, 2147483647).

import java.math.BigInteger

/**
 * @param n initial number of beers on the wall
 * @return Pair(number of iterations needed to remove all the bottles, number of bottles removed in the last iteration)
 */
fun bottlesOfBeer(n: BigInteger): Pair<BigInteger, BigInteger> {
    require(n >= BigInteger.ZERO)

    if (n == BigInteger.ZERO) return Pair(BigInteger.ZERO, BigInteger.ZERO);
    if (n == BigInteger.ONE) return Pair(BigInteger.ONE, BigInteger.ONE);

    val numberOfIterations = findIndex(n);
    val sum = sumFromOneTo(numberOfIterations);

    return if (sum != n) {
        Pair(numberOfIterations.inc(), n - sum);
    } else {
        Pair(numberOfIterations, n - sumFromOneTo(numberOfIterations.dec()))
    }
}

/**
 * Calculate the sum using arithmetic progression formula (a1=1, d=1) with O(1) complexity
 * @param n positive number
 * @return sum of all numbers from 1 to n inclusive (1+2+...+(n-1)+n)
 */
fun sumFromOneTo(n: BigInteger): BigInteger {
    require(n >= BigInteger.ONE);

    return n * (n + BigInteger.ONE) / (2.toBigInteger());
}

/**
 * @param n positive number
 * @return i: (sumFromOneTo(i) <= n) and (sumFromOneTo(i + 1) > n)
 */
private fun findIndex(n: BigInteger): BigInteger {
    require(n >= BigInteger.ONE);

    return binarySearchIndex(BigInteger.ONE, n, n);
}

private fun checkIndex(i: BigInteger, n: BigInteger): Boolean {
    require(i >= BigInteger.ONE);
    require(n >= BigInteger.ONE);

    return (sumFromOneTo(i) <= n) && (sumFromOneTo(i.inc()) > n);
}

/**
 * @param start start of the search interval
 * @param end end of the search interval
 * @param n positive number
 * @return i: (sumFromOneTo(i) <= n) and (sumFromOneTo(i + 1) > n) and (start <= i <= end)
 */
private fun binarySearchIndex(start: BigInteger, end: BigInteger, n: BigInteger): BigInteger {
    require(start >= BigInteger.ONE);
    require(start <= end);
    require(n >= BigInteger.ONE);

    if (checkIndex(start, n)) return start;
    if (checkIndex(end, n)) return end;

    require(start != end) { "Index does not exist" };

    val mid = (start + end) / 2.toBigInteger();
    val sumToMid = sumFromOneTo(mid);

    return if (sumToMid > n) {
        binarySearchIndex(start, mid, n);
    } else {
        binarySearchIndex(mid, end, n);
    }
}