当前位置:网站首页>LeetCode每日一题(1362. Closest Divisors)
LeetCode每日一题(1362. Closest Divisors)
2022-07-03 09:01:00 【wangjun861205】
Given an integer num, find the closest two integers in absolute difference whose product equals num + 1 or num + 2.
Return the two integers in any order.
Example 1:
Input: num = 8
Output: [3,3]
Explanation: For num + 1 = 9, the closest divisors are 3 & 3, for num + 2 = 10, the closest divisors are 2 & 5, hence 3 & 3 is chosen.
Example 2:
Input: num = 123
Output: [5,25]
Example 3:
Input: num = 999
Output: [40,25]
Constraints:
- 1 <= num <= 10^9
最优解当然是 n² = num + 1 或者 n² = num + 1, 因为 1 <= num <= 1000000000, 那我们的 n 自然不会大于 40000, 有了这个条件托底, 我们就算用最简单的方法从 40000 一路试到 1 也可以, 当然, 最好是把 n 先判断出来
impl Solution {
pub fn closest_divisors(num: i32) -> Vec<i32> {
if num == 1 {
return vec![1, 2];
}
let num = num as i64;
// 指数
let mut e = 1u32;
loop {
if 2i64.pow(e) >= num {
break;
}
e += 1;
}
// 计算出n的上限
let n = 2i64.pow(e / 2 + e % 2);
let mut a = i64::MAX;
let mut b = 0;
for v in (1..=n).rev() {
if (num + 1) % v == 0 {
if ((num + 1) / v - v).abs() < (a - b).abs() {
a = (num + 1) / v;
b = v;
}
}
if (num + 2) % v == 0 {
if ((num + 2) / v - v).abs() < (a - b).abs() {
a = (num + 2) / v;
b = v;
}
}
}
vec![a as i32, b as i32]
}
}
边栏推荐
- LeetCode每日一题(1300. Sum of Mutated Array Closest to Target)
- 2022-1-6 Niuke net brush sword finger offer
- With low code prospect, jnpf is flexible and easy to use, and uses intelligence to define a new office mode
- [point cloud processing paper crazy reading classic version 12] - foldingnet: point cloud auto encoder via deep grid deformation
- We have a common name, XX Gong
- Flink学习笔记(八)多流转换
- What are the stages of traditional enterprise digital transformation?
- Notes on numerical analysis (II): numerical solution of linear equations
- Use the interface colmap interface of openmvs to generate the pose file required by openmvs mvs
- [point cloud processing paper crazy reading classic version 11] - mining point cloud local structures by kernel correlation and graph pooling
猜你喜欢
【点云处理之论文狂读经典版7】—— Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs
Construction of simple database learning environment
Vs2019 configuration opencv3 detailed graphic tutorial and implementation of test code
[point cloud processing paper crazy reading classic version 7] - dynamic edge conditioned filters in revolutionary neural networks on Graphs
[point cloud processing paper crazy reading classic version 12] - foldingnet: point cloud auto encoder via deep grid deformation
Recommend a low code open source project of yyds
[point cloud processing paper crazy reading classic version 10] - pointcnn: revolution on x-transformed points
[kotlin learning] operator overloading and other conventions -- overloading the conventions of arithmetic operators, comparison operators, sets and intervals
Idea uses the MVN command to package and report an error, which is not available
[point cloud processing paper crazy reading classic version 13] - adaptive graph revolutionary neural networks
随机推荐
Spark 集群安装与部署
Word segmentation in full-text indexing
Detailed steps of windows installation redis
【点云处理之论文狂读经典版13】—— Adaptive Graph Convolutional Neural Networks
[point cloud processing paper crazy reading classic version 9] - pointwise revolutionary neural networks
Spark 概述
LeetCode每日一题(1300. Sum of Mutated Array Closest to Target)
2022-2-14 learning xiangniuke project - Session Management
[solution to the new version of Flink without bat startup file]
IDEA 中使用 Hudi
MySQL installation and configuration (command line version)
[kotlin learning] operator overloading and other conventions -- overloading the conventions of arithmetic operators, comparison operators, sets and intervals
About the configuration of vs2008+rade CATIA v5r22
【Kotlin学习】类、对象和接口——带非默认构造方法或属性的类、数据类和类委托、object关键字
【Kotlin学习】类、对象和接口——定义类继承结构
[point cloud processing paper crazy reading frontier edition 13] - gapnet: graph attention based point neural network for exploring local feature
2022-1-6 Niuke net brush sword finger offer
Integrated use of interlij idea and sonarqube
Hudi learning notes (III) analysis of core concepts
State compression DP acwing 291 Mondrian's dream