# interview

## 在不發生 integer overflow 的情況下讓一組數字做平均計算

錯誤的解決方法:

const NEW_NUM_MAX_LENGTH = 4;

class NewNumber {
  constructor(originalNumber) {
    this.value = [];
    this.maxNumber = Math.pow(10, NEW_NUM_MAX_LENGTH);
    this.originalNumber = originalNumber;

    if(!Number.isInteger(originalNumber)) throw new Error(`Original number must be integer, got ${this.originalNumber}`);
    if(this.originalNumber > 0 && (this.originalNumber/this.maxNumber) >= 1) throw new Error(`Original number must be less than ${this.maxNumber}`);
    if(this.originalNumber < 0 && (this.originalNumber/this.maxNumber) <= -1) throw new Error(`Original number must be more than -${this.maxNumber}`);

    let _middleNumber = this.originalNumber;
    while(_middleNumber > 0) {
      this.value.push(_middleNumber%10);
      _middleNumber = parseInt(_middleNumber/10);
    }

    const lackOfNumberLength = NEW_NUM_MAX_LENGTH-this.value.length;
    if (lackOfNumberLength > 0) {
      for(let i=0; i<lackOfNumberLength; i++) {
        this.value.push(0);
      }
    }
  }
  getNumber() {
    // return this.value.reverse().reduce((a,b)=> a*10+b,0)
    return this.originalNumber;
  }
}

function saveAddUp(numberA, numberB) {
  if (numberA instanceof NewNumber && numberB instanceof NewNumber) {
    let result = [];
    for (let i = 0; i<NEW_NUM_MAX_LENGTH; i++) {
      result.push(numberA.value[i] + numberB.value[i]);
    }
    result = carry(result);
    check(result); // 檢查第最後一位是否 overflow
    
    // 總和後轉換成新的 number
    result = new NewNumber(result.reverse().reduce((a,b)=> a*10+b,0));
    return result;
  } else {
    throw new Error('Both of number A and number B must be NewNumber type');
  }
}

function carry(number) {
  const newNumber = [];
  for (let i=0; i<NEW_NUM_MAX_LENGTH; i++) {
    if (i<NEW_NUM_MAX_LENGTH-1) {
      // 只做到第三位, 因為第四位永遠不會進位, 如果有進位的 case, 留到 check 階段去排除
      const numberInThisDigit = number[i]%10;
      newNumber.push(numberInThisDigit);
      const numberAddToNextDigit = parseInt(number[i]/10);
      number[i+1] += numberAddToNextDigit;
    } else {
      const numberInThisDigit = number[i];
      newNumber.push(numberInThisDigit);
    }
  }
  return newNumber;
};

function check(number) {
  if (number[NEW_NUM_MAX_LENGTH-1]>=10) throw new Error('Add result will overflow');
}

function mean(numbersInList) {
  let result = new NewNumber(0);
  let remainder = 0;
  for (let i = 0; i<numbersInList.length; i++) {
    const newTestNumber = new NewNumber(numbersInList[i]);
    result = saveAddUp(result, newTestNumber);

    // 第二筆之後都需要除以 2
    if(i>0) {
      let tmpResult = [];
      for (let i = (result.value.length-1); i>=0; i-=1) {
        const digitResult = result.value[i]/2;
        tmpResult.push(parseInt(digitResult));

        if (digitResult>=1) {
          // 如果大於等於一, 取餘數後乗十加上下一位數
          if (i>0) {
            result.value[i-1] += (result.value[i]%2)*10;
          } else {
            remainder = (digitResult - parseInt(digitResult));
          }
        } else {
          // 如果小於一, 直接乗十加上下一位數
          if (i>0) {
            result.value[i-1] += result.value[i]*10;
          } else {
            remainder = (digitResult - parseInt(digitResult));
          }
        }
      }
      // 總和後轉換成新的 number
      result = new NewNumber(tmpResult.reduce((a,b)=> a*10+b,0));
    }
  }
  return result.getNumber()+remainder;
}

const numberList = [127, 64];
console.log(numberList);
const meanOfNumber = mean(numberList);
console.log(meanOfNumber);