Skip to content

Latest commit

 

History

History
49 lines (42 loc) · 887 Bytes

754.到达终点数字.md

File metadata and controls

49 lines (42 loc) · 887 Bytes

754.到达终点数字

/*
 * @lc app=leetcode.cn id=754 lang=typescript
 *
 * [754] 到达终点数字
 */

// @lc code=start
function reachNumber(target: number): number {}
// @lc code=end

解法 1: 二分

function reachNumber(target: number): number {
  const check = (t: number) => {
    return t + (t * (t - 1)) / 2 >= target
  }
  let l = 1,
    r = target + 10
  while (l < r) {
    const m = Math.floor((l + r) / 2)
    if (check(m)) {
      r = m
    } else {
      l = m + 1
    }
  }

  for (; ; l++) {
    if ((l + (l * (l - 1)) / 2) % 2 === target % 2) return l
  }
}

Case

test.each([
  { input: { target: 10 ** 5 }, output: 447 },
  { input: { target: 2 }, output: 3 },
  { input: { target: 3 }, output: 2 },
])('input: target = $input.target', ({ input: { target }, output }) => {
  expect(reachNumber(target)).toEqual(output)
})