java 查找范围内数字的除数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/25661519/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find the number of divisors for a number in range
提问by drevlav
I have a question regarding the CountDivproblem in Codility.
我有一个关于Codility中的CountDiv问题的问题。
The problem given is: Write a function:
给出的问题是：写一个函数：
class Solution { public int solution(int A, int B, int K); }
that, given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K, i.e.:
给定三个整数 A、B 和 K，返回范围 [A..B] 内可被 K 整除的整数的数量，即：
{ i : A ≤ i ≤ B, i mod K = 0 }
My code:
我的代码：
class Solution {
public int solution(int A, int B, int K) {
int start=0;
if (B<A || K==0 || K>B )
return 0;
else if (K<A)
start = K * ( A/K +1);
else if (K<=B)
start = K;
return (B-start+1)/K+ 1;
}
}
I don't get why I'm wrong, specially with this test case:
我不明白为什么我错了，特别是这个测试用例：
extreme_ifempty
A = 10, B = 10, K in {5,7,20}
WRONG ANSWER
got 1 expected 0
if K =5then with i=10A<=i<=Band i%k =0so why should I have 0? Problem statement.
如果K =5再与i=10A<=i<=B和i%k =0，所以我为什么应该有0？问题陈述。
回答by Pham Trung
This is the O(1) solution, which passed the test
这是 O(1) 解决方案，它通过了测试
int solution(int A, int B, int K) {
int b = B/K;
int a = (A > 0 ? (A - 1)/K: 0);
if(A == 0){
b++;
}
return b - a;
}
Explanation: Number of integer in the range [1 .. X]that divisible by Kis X/K. So, within the range [A .. B], the result is B/K - (A - 1)/K
说明：号码范围整数[1 .. X]那整除K的X/K。所以，在范围内[A .. B]，结果是B/K - (A - 1)/K
In case A is 0, as 0 is divisible by any positive number, we need to count it in.
如果 A 为 0，因为 0 可以被任何正数整除，我们需要将其计入。
回答by moxi
Java solution with O(1) and 100% in codility, adding some test cases with solutions for those who want to try and not see others solutions:
具有 O(1) 和 100% codility 的 Java 解决方案，为那些想尝试但看不到其他解决方案的人添加了一些带有解决方案的测试用例：
// Test cases
// [1,1,1] = 1
// [0,99,2] = 50
// [0, 100, 3] = 34
// [11,345,17] = 20
// [10,10,5] = 1
// [3, 6, 2] = 2
// [6,11,2] = 3
// [16,29,7] = 2
// [1,2,1] = 2
public int solution(int A, int B, int K) {
int offsetForLeftRange = 0;
if ( A % K == 0) { ++offsetForLeftRange; }
return (B/K) - (A /K) + offsetForLeftRange;
}
回答by cheshy
The way to solve this problem is by Prefix Sums as this is part of that section in Codility.
解决这个问题的方法是通过前缀和，因为这是 Codility 中该部分的一部分。
https://codility.com/programmers/lessons/3/
https://codility.com/programmers/lessons/3/
https://codility.com/media/train/3-PrefixSums.pdf
https://codility.com/media/train/3-PrefixSums.pdf
Using this technique one can subtract the count of integers between 0 and A that are divisible by K (A/K+1) from the the count of integers between 0 and B that are divisible by K (B/K+1).
使用这种技术，可以从 0 和 B 之间可被 K 整除的整数的计数 (B/K+1) 中减去 0 和 A 之间可被 K 整除的整数的计数 (A/K+1)。
Remember that A is inclusive so if it is divisible then include that as part of the result.
请记住， A 是包含性的，因此如果它可整除，则将其作为结果的一部分包含在内。
Below is my solution:
以下是我的解决方案：
class Solution {
public int solution(int A, int B, int K) {
int b = (B/K) + 1; // From 0 to B the integers divisible by K
int a = (A/K) + 1; // From 0 to A the integers divisible by K
if (A%K == 0) { // "A" is inclusive; if divisible by K then
--a; // remove 1 from "a"
}
return b-a; // return integers in range
}
}
回答by HelpVampire666
return A==B ? (A%K==0 ? 1:0) : 1+((B-A)/K)*K /K;
Well it is a completely illegible oneliner but i posted it just because i can ;-)
嗯，它是一个完全难以辨认的单线，但我发布它只是因为我可以;-)
complete java code here:
完整的java代码在这里：
package countDiv;
public class Solution {
/**
* First observe that
* <li> the amount of numbers n in [A..B] that are divisible by K is the same as the amount of numbers n between [0..B-A]
* they are not the same numbes of course, but the question is a range question.
* Now because we have as a starting point the zero, it saves a lot of code.
* <li> For that matter, also A=-1000 and B=-100 would work
*
* <li> Next, consider the corner cases.
* The case where A==B is a special one:
* there is just one number inside and it either is divisible by K or not, so return a 1 or a 0.
* <li> if K==1 then the result is all the numbers between and including the borders.
* <p/>
* So the algorithm simplifies to
* <pre>
* int D = B-A; //11-5=6
* if(D==0) return B%K==0 ? 1:0;
* int last = (D/K)*K; //6
* int parts = last/K; //3
* return 1+parts;//+1 because the left part (the 0) is always divisible by any K>=1.
* </pre>
*
* @param A : A>=1
* @param B : 1<=A<=B<=2000000000
* @param K : K>=1
*/
private static int countDiv(int A, int B, int K) {
return A==B ? A%K==0 ? 1:0 : 1+((B-A)/K)*K /K;
}
public static void main(String[] args) {
{
int a=10; int b=10; int k=5; int result=1;
System.out.println( a + "..." + b + "/" + k + " = " + countDiv(a,b,k) + (result!=countDiv(a,b,k) ? " WRONG" :" (OK)" ));
}
{
int a=10; int b=10; int k=7; int result=0;
System.out.println( a + "..." + b + "/" + k + " = " + countDiv(a,b,k) + (result!=countDiv(a,b,k) ? " WRONG" :" (OK)" ));
}
{
int a=6; int b=11; int k=2; int result=3;
System.out.println( a + "..." + b + "/" + k + " = " + countDiv(a,b,k) + (result!=countDiv(a,b,k) ? " WRONG" :" (OK)" ));
}
{
int a=6; int b=2000000000; int k=1; int result=b-a+1;
System.out.println( a + "..." + b + "/" + k + " = " + countDiv(a,b,k) + (result!=countDiv(a,b,k) ? " WRONG" :" (OK)" ));
}
}
}//~countDiv
回答by Caesar Avgvstvs
This is my 100/100 solution:
这是我的 100/100 解决方案：
https://codility.com/demo/results/trainingRQDSFJ-CMR/
https://codility.com/demo/results/trainingRQDSFJ-CMR/
class Solution {
public int solution(int A, int B, int K) {
return (B==0) ? 1 : B/K + ( (A==0) ? 1 : (-1)*(A-1)/K);
}
}
Key aspects of this solution:
该解决方案的关键方面：
- If A=1, then the number of divisors are found in B/K.
- If A=0, then the number of divisors are found in B/K plus 1.
- If B=0, then there is just one i%K=0, i.e. zero itself.
- 如果 A=1，则在 B/K 中找到除数的数量。
- 如果 A=0，则在 B/K 加 1 中找到除数的数量。
- 如果 B=0，则只有一个 i%K=0，即零本身。
回答by Amrit Malla
Here is my simple solution, with 100% https://app.codility.com/demo/results/trainingQ5XMG7-8UY/
这是我的简单解决方案，100% https://app.codility.com/demo/results/trainingQ5XMG7-8UY/
public int solution(int A, int B, int K) {
while (A % K != 0) {
++A;
}
while (B % K != 0) {
--B;
}
return (B - A) / K + 1;
}
回答by Ramiz
I think the answers above don't provide enough logical explanation to why each solution works (the math behind the solution) so I am posting my solutionhere.
我认为上面的答案没有提供足够的逻辑解释为什么每个解决方案都有效（解决方案背后的数学），所以我在这里发布我的解决方案。
The idea is to use the arithmetic sequencehere. If we have first divisible number (>= A) and last divisible number (<= B) we have an arithmetic sequence with distance K. Now all we have to do is find the total number of terms in the range [newA, newB] which are total divisible numbers in range [newA, newB]
这个想法是在这里使用等差数列。如果我们有第一个可整除数 (>= A) 和最后一个可整除数 (<= B)，我们就有一个距离为 K 的等差数列。现在我们要做的就是找到范围 [newA, newB] 中的项总数它们是 [newA, newB] 范围内的可整除数
first term (a1) = newA
last/n-th term (an) = newB
distance (d) = K
Sn = a1 + (a1+K) + (a1 + 2k) + (a1 + 3k) + ... + (a1 + (n-1)K)
`n` in the above equation is what we are interested in finding. We know that
n-th term = an = a1 + (n-1)K
as an = newB, a1 = newA so
newB = newA + (n-1)K
newB = newA + nK - K
nK = newB - newA + K
n = (newB - newA + K) / K
Now that we have above formula so just apply it in code.
现在我们有了上面的公式，所以只需在代码中应用它。
fun countDiv(A: Int, B: Int, K: Int): Int {
//NOTE: each divisible number has to be in range [A, B] and we can not exceed this range
//find the first divisible (by k) number after A (greater than A but less than B to stay in range)
var newA = A
while (newA % K != 0 && newA < B)
newA++
//find the first divisible (by k) number before B (less than B but greater than A to stay in range)
var newB = B
while (newB % K != 0 && newB > newA)
newB--
//now that we have final new range ([newA, newB]), verify that both newA and newB are not equal
//because in that case there can be only number (newA or newB as both are equal) and we can just check
//if that number is divisible or not
if (newA == newB) {
return (newA % K == 0).toInt()
}
//Now that both newA and newB are divisible by K (a complete arithmetic sequence)
//we can calculate total divisions by using arithmetic sequence with following params
//a1 = newA, an = newB, d = K
// we know that n-th term (an) can also be calculated using following formula
//an = a1 + (n - 1)d
//n (total terms in sequence with distance d=K) is what we are interested in finding, put all values
//newB = newA + (n - 1)K
//re-arrange -> n = (newB - newA + K) / K
//Note: convert calculation to Long to avoid integer overflow otherwise result will be incorrect
val result = ((newB - newA + K.toLong()) / K.toDouble()).toInt()
return result
}
I hope this helps someone. FYI, codility solution with 100% score
我希望这可以帮助别人。仅供参考，100% 得分的 codility 解决方案
回答by Allen Wang
Here's my solution, two lines of Java code.
这是我的解决方案，两行 Java 代码。
public int solution(int A, int B, int K) {
int a = (A == 0) ? -1 : (A - 1) / K;
return B / K - a;
}
The thought is simple.
a refers to how many numbers are divisible in [1..A-1]
B / K refers to how many numbers are divisible in [1..B]
0 is divisible by any integer so if A is 0, you should add one to the answer.
想法很简单。
a 指的是 [1..A-1] 中有多少个数字可以整除
B / K 指的是 [1..B] 中有多少个数字可以整除
0 可以被任何整数整除，所以如果 A 是 0，你应该加一个到答案。
回答by adrianekafikri
Here is my solution and got 100%
这是我的解决方案并获得了 100%
public int solution(int A, int B, int K) {
int count = B/K - A/K;
if(A%K == 0) {
count++;
}
return count;
}
- B/K will give you the total numbers divisible by K [1..B]
- A/K will give you the total numbers divisible by K [1..A]
- then subtract, this will give you the total numbers divisible by K [A..B]
- check A%K == 0, if true, then + 1 to the count
- B/K 将为您提供可被 K 整除的总数 [1..B]
- A/K 将为您提供可被 K [1..A] 整除的总数
- 然后减去，这将为您提供可被 K [A..B] 整除的总数
- 检查 A%K == 0，如果为真，则 + 1 到计数
回答by Abdullah
int solution(int A, int B, int K) {
int tmp=(A%K==0?1:0);
int x1=A/K-tmp ;
int x2=B/K;
return x2-x1;
}
