面试题库 › 嵌入式 › 找最小正整数M使N乘M只由0和1组成

找最小正整数M使N乘M只由0和1组成

难度 ★★★在 1 场真实面经中被问到 方向:嵌入式考点:数学与智力题

哪些公司问过

寒武纪1

常见岗位:驱动与底层

答案要点

  1. 转化为找N的最小0/1倍数X,M=X/N
  2. 按余数做BFS:r→(10r)%N和(10r+1)%N,起点为1
  3. 先扩展添0分支,首次到达余数0即为最小X
  4. 记录前驱回溯构造X,再做大数除法得到M
  5. 余数最多N个状态,时间空间O(N);抽屉原理保证有解

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题