CareerCup

c++, binary search

typedef unsigned short UINT16;

const UINT16 MAX_UINT16 = 65535;

UINT16 withdrawAll() {
	UINT16 money, all;

	money = MAX_UINT16;
	all = 0;
	while (money) {
		if (withdraw(money) == 0) {
			money /= 2;
		} else {
			all += money;
		}
	}

	return all;
}

// You have some money in you bank account, the only function to
// withdraw money is `uint_16t withdraw(uint_16t value)`.  If `value`
// is greater than they money you have it returns 0, otherwise it
// withdraws the requested amount and returns the "value".

// Write a function that withdraws all your money.

"use strict";

const withdraw = require('./uint_16t-bank-account-withdraw');

module.exports = function () {
	let money = 0;
	let value = 65535;
	let withdrawal;

	while (value > 0) {
		while (withdrawal = withdraw(value)) {
			money += withdrawal;
		}
		value = Math.floor(value / 2);
	}

	return money;
};

I would start from amount = 1 and double the amount each time the transaction is successful.
When we get unsuccessful transaction we divide amount by 2 each time until we reach empty account (basically when we can't withdraw 1):

int amount = 1;

while (account.withdraw(amount) > 0) {
    amount *= 2;
}

while (!(amount == 1 && account.withdraw(amount) == 0)) {
    account.withdraw(amount);

    if (amount > 1) {
        amount /= 2;
    }
}

uint16 means that you can only withdraw money 65535 each time. But the total money in the bank maybe very very big

Weird question. I can smell incremental binary search here but again what he was looking for is something only he will know.

void allMonies()
{
  int allMonies = 100;
  int counter = 1;
	bool upHill = true;
  while(true)
  {
	  std::cout << allMonies << " " << counter << "\n";
    if(allMonies-counter>0)
		{
		  allMonies -= counter;
			counter *= 2;
		}
		else
		{
      counter /= 2;
			if(!counter)
				break;
		}
  }
}

Assuming our maximum amount of money is a 16 bit number, we can incrementally remove from the account the value of each bit in the number if its set, starting from the last bit.

For example, say we have $16972 in the account.

Try 32768 --> too big, nothing removed.
Try 16384 --> take it! (Left is 588)
Try 8192 --> too big, nothing removed.
...
Try 512 --> take it! (Left is 76)
...
Try 64 --> take it! (Left is 12)
..
Try 8 --> take it! (Left is 4)
Try 4 --> take it! (left is 0)
...
Done.

C++

UINT16 withdrawAll()
{
	UINT16 total = 0;
	UINT16 amount = 1 << 15;
	while(amount > 0)
	{
		total += withdraw(amount);
		amount = amount >> 1;
	}
	return total;
}

Complexity: O(16) -> O(1)

int WithdowAllMoney()
{
uint16_t value = UINT16_MAX;
int moneyTaken = 0;

while (value)
{
uint16_t current = Withdrow(value);
if (current)
{
moneyTaken += current;
}
value = value >> 1;
}

moneyTaken += Withdrow(1);

return moneyTaken;
}

int WithdowAllMoney()
{
    uint16_t value = UINT16_MAX;
    int moneyTaken = 0;
    while (value)
    {
        uint16_t current = Withdrow(value);
        if (current)
        {
            moneyTaken += current;
        }
        value = value >> 1;
    }
    moneyTaken += Withdrow(1);
    return moneyTaken;
}

int WithdowAllMoney()
{
    uint16_t value = UINT16_MAX;
    int moneyTaken = 0;

    while (value)
    {
        uint16_t current = Withdrow(value);
        if (current)
        {
            moneyTaken += current;
        }
        value = value >> 1;
    }

    moneyTaken += Withdrow(1);

    return moneyTaken;

}

Groovy code with int64 type instead of uint16.

long withdrawAll(long luckyStrike) {
        if (luckyStrike < 1) { return 0 }
        
        int funds = withdraw(luckyStrike)
        if (funds != 0) {
            return funds + withdrawAll(luckyStrike * 2) // care type overflow
        } else {
            return withdrawAll(luckyStrike / 2)
        }   
    }

void funny() {
	uint16 value = 65535;
	START:
	while (withdraw(value));
	if (value >>= 1) goto START;	
}

{
void withdrawAll() {
uint16 max = (uint16) ~0;
uint16 withdrawn = 0;
while(max) {
withdrawn += withdraw(max);
max >>= 1;
}
}
}

void withdrawAll() {
uint16 max = (uint16) ~0;
uint16 withdrawn = 0;
while(max) {
withdrawn += withdraw(max);
max >>= 1;
}
}

My C# implementation

public void WithdrawAll()
{
   int maxValue = (int)Math.Pow(2, 16);

   while (Withdraw(maxValue) > 0);

   while (maxValue > 0)
   {
	   Withdraw(maxValue);
	   maxValue /= 2;
   }
}

Here is C++ version of solution.

Running in log n.

#include<iostream>
#include <cstdint>
using namespace std;

class Account {

public:	
	Account(uint16_t amount):left(amount){}

	uint16_t withdraw(uint16_t value)
	{
		if (left < value)
			return 0;
		else
		{
			left -= value;
			return value;
		}
	}

	uint16_t print()
	{
		cout<<"left = " <<left<<endl;
	}

private:
	uint16_t left;
};


void withdraw_all(uint16_t amount)
{
	uint16_t value = UINT16_MAX;
	Account a(amount);

	uint16_t total = 0;
	int count = 0;

	while (total != amount)
	{
		int returned = a.withdraw(value);
		if (!returned)
			value = value/2;
		else if (returned < value)
		{
			value = (returned > value/2)? returned: value/2;
		} 
		total += returned;
		count++;
	}
	cout <<"withdrew : "<< total<<" from "<<amount <<" in "<<count<< " attampts"<<endl;
}

In Golang

package main

import (
	"fmt"
)

const MAX_WITHDRAW_AMT = ^uint16(0)

type Account struct {
	balance int
}

func createAccount(balance int) *Account {
	return &Account{balance: balance}
}

func (a *Account) withdraw(amt uint16) uint16 {
	if a.balance >= int(amt) {
		a.balance = a.balance - int(amt)
		return uint16(amt)
	}
	return 0
}

func withdrawAll(a *Account) (int, int) {
	numCalls := 0
	totalAmtWithdrawn := 0
	lastAmtWithdrawn := 0
	withdrawAmt := uint16(MAX_WITHDRAW_AMT)

	for withdrawAmt > 0 {
		lastAmtWithdrawn = int(a.withdraw(withdrawAmt))
		if lastAmtWithdrawn == 0 {
			withdrawAmt = withdrawAmt / 2
		} else {
			totalAmtWithdrawn += lastAmtWithdrawn
		}
		numCalls += 1
	}

	return totalAmtWithdrawn, numCalls
}

func main() {
	var withdrawnAmt int
	var numCallsMade int
	balance := 273717
	account := createAccount(balance)
	withdrawnAmt, numCallsMade = withdrawAll(account)
	fmt.Println(fmt.Sprintf("$%d out of $%d withdrawn on %d calls to withdraw()", balance, withdrawnAmt, numCallsMade))

	balance = 27372
	account = createAccount(balance)
	withdrawnAmt, numCallsMade = withdrawAll(account)
	fmt.Println(fmt.Sprintf("$%d out of $%d withdrawn on %d calls to withdraw()", balance, withdrawnAmt, numCallsMade))

	balance = 283
	account = createAccount(balance)
	withdrawnAmt, numCallsMade = withdrawAll(account)
	fmt.Println(fmt.Sprintf("$%d out of $%d withdrawn on %d calls to withdraw()", balance, withdrawnAmt, numCallsMade))

	balance = int(^uint32(0) >> 1)
	account = createAccount(balance)
	withdrawnAmt, numCallsMade = withdrawAll(account)
	fmt.Println(fmt.Sprintf("$%d out of $%d withdrawn on %d calls to withdraw()", balance, withdrawnAmt, numCallsMade))
}