DSA 4: Big-O - Chessboard & Grains Problem

Question 3. Chess Board Algorithm

Imagine you have a chessboard ♟️, and:

• One one square put a single grain of rice
• On the second square, you put two grains of rice, since that is double the amount of rice on the previous square.
• On the third square, you put four grains.
• On the fourth square, you put eight grains, and
• On the fifth square, you put sixteen grains, and so on.

Q. Use \(Big\_O\) notation to describe the \(Time\ Complexity\):

Q. Write a function to calculate which square you’ll need to place a certain number of rice grains.

For example, for sixteen grains:

• the function will return 5, since you will
• place the sixteen grains on the fifth square.

Reference:

• Wheat and chessboard problem (wiki)

3.1 Written Solution

We can define:

• For each step (chessboard square), it is incremented by one,
  • placed_grains is the number grains placed down on the square
    • This number doubles at each step.
  • placed_grains is calculated by an algorithm of \(log\ time\) or \(O(\log{N})\)
    • Increases one step each time the data doubles,
    • and so equivalently,
    • Move to next chessboard square, double placed grains

In other words:

• \(O(\log{N})\) means that for N data elements, the algorithm would take \(\log_{2}{N}\) steps.

3.2 Expected Results: Placed Grains Table

To find out:

• Which chessboard square (step)
• Contains 16 grains on the square (n_grains=16)
• Double the number of grains placed (placed_grain) at each step until we reached the desired amount of grains (placed_grain==n_grains):
  • chessboard square: 5 (step=5)

step	placed_grain	n_grains
1	1	16
2	2	16
3	4	16
4	8	16
5	16	16

3.3 Python for-loop explainer

for-loops are useful when:

• Scenario: The range of iteration is known:

  • or min and max of our iteration
  • or start (arg 1) and stop (arg 2) indexes are known in advance
  • boolean rule not required.
    • The loop will stop automatically when the limit is reached

• The chessboard has \(64\) squares: the range would be:

  • from 1 to 64
  • Note: The loop counts up to but does not include the stop value
    • range(1,64): counts 1,2,..63, thus use
    • range(1,65): counts 1,2,..64

3.4 Python while-loop explainer

while-loops are useful when:

• Scenario: The range of iteration is unknown:

  • a min or start argument required
    • manual iteration required
  • boolean rule is required.
    • The loop will exit when rule is not True or False anymore (i.e. goal has been reached)
    • The loop will continue forever unless the goal is reached
      • Note: careful consideration to ensure the boolean test is reachable

• The loop does not care how many squares the chessboard has (unless manually placed as a requirement)

3.5 for-loop Solution

### Answer 1: for-loop ###
idx=1
max_squares = 64
placed_grains = 1
target_grains = 16
for i in range(1,max_squares+1):
    if placed_grains == target_grains:
        print(idx)
        break
        # return idx
    idx+=1
    placed_grains=placed_grains*2
# [1,2,3,4, 5, 6, 7]
# [1,2,4,8,16,32,64]

5

3.6 while-loop Solution

### Answer 2: while-loop ###
idx = 1
placed_grains = 1
target_grains = 16

while placed_grains<target_grains:
    idx+=1
    placed_grains*=2

print(idx)

5