## DEV Community is a community of 906,671 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Daily Challenge #111 - 99 Bottles of Beer

You all know the lyrics to the song "99 Bottles of Beer on the Wall", right? If not check out this link.

Instead of removing just one bottle in each iteration, we want to remove one more bottle than in the previous iteration (i.e. start with 99, then 98, then 96, 93, 89, etc.)

The Challenge: Write a method that takes the initial number of beers on the wall and returns the number of iterations needed to remove all the bottles, in addition to providing the number of bottles removed in the last iteration. (as a tuple or as a string).

Bonus — do the math, not just a simple loop (because that wouldn't be much of a challenge, would it?)

Good luck!

This challenge comes from @peledzohar here on DEV. Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

## Discussion (5) kesprit • Edited on

My solution in Swift (without Bonus it's saturday 😛) :

``````func numberOfBottles(numberOfBottle: Int) -> (restOfBottles: Int, loop:Int) {
guard numberOfBottle > 0 else { return (0,0) }
guard numberOfBottle != 1 else { return (1,1) }
var number = 1
var loop = 0
var numberOfBottle = numberOfBottle

while (numberOfBottle - number) > 0 {
loop += 1
numberOfBottle -= number
number += 1
}
return (numberOfBottle,loop)
}
``````

Edit: Thank you to @vo_kononenko for to find my mistake Vitaliy Kononenko

It looks like `number *= 2` at the end of the loop should be replaced with `number += 1`, because the number of removed bottles on each iteration increases by 1, not doubles. Vitaliy Kononenko • Edited on

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);
}
}
`````` Jon Bristow

This is as close as I can get to “no string declared more than once”

``````module Beer
( song
) where

import qualified Data.Char as Char
import qualified Data.List as List

bottlesOfBeer :: Int -> String
bottlesOfBeer n = " bottle" ++ plural ++ " of beer"
where
plural =
case n of
1 -> ""
_ -> "s"

onTheWall :: Int -> String
onTheWall n = howMany n ++ " on the wall"

howMany :: Int -> String
howMany n = countStr ++ bottlesOfBeer n
where
countStr =
case n of
0 -> "no more"
_ -> show n

capitalize :: String -> String
capitalize (h:r) = Char.toUpper h : r

line2start :: Int -> String
line2start 0 = "Go to the store and buy some more"
line2start n = "Take " ++ theOne ++ " down and pass it around"
where
theOne =
case n of
1 -> "it"
_ -> "one"

next 0 = 99
next n = pred n

outputLine :: [Int -> String] -> Int -> String
outputLine fs = List.intercalate ", " . sequence fs

verse :: Int -> String
verse =
List.intercalate "" .
map (++ ".\n") .
mapM
outputLine
[[capitalize . onTheWall, howMany], [line2start, onTheWall . next]]

song :: String
song = List.intercalate "\n" \$ map verse [99,98 .. 0]
``````