S*********2
发帖数: 172 | 1 Given an array with length at least 1 and not more than 100. write a
function which returns total pair of (a, b) in the array. Any pair start
looping till they are equal. when a < b, a double itself. then b decrease
by a.
Vice versa. For example, 1,4 -> 2, 3 ->4, 1 -> 3, 2 -> 1, 4 and so on.
Therefore,(1,4)
count for a pair. 3,5 -> 6,2 -> 4,4, stop at 4== 4. so (3,5) is not a pair.
a, b < 2^30 -1.
code总是TLE， 请问有效率的判断方法，谢谢！
下面是我的code总是超时
public class solution{
public static int solution(int[] arr) {
int len = arr.length;
int cnt = 0;
for (int i = 0; i < len-1; i++) {
for (int j = i+1; j < len; j++) {
if (isPairable(arr[i],arr[j])) cnt++;
}
}
return cnt;
}
private static boolean isPairable(int i, int j) {
if (i == j) return false;
if ((i+j)%2 == 1 || ((i+j)/2)%2 == 1) return true;
if (j < i) {i = i-j; j =j+i; i = j-i;}
Set set = new HashSet();
int mid,t;
mid = (i+j)/2;
t = mid/i;
if (mid%i == 0 && (t == (t & -t))) return false;
while (i < j) {
if (set.contains(i)) return true;
set.add(i);
j = j - i;
i = i+i;
if (i > j) {
i = i-j; j = j+i; i = j-i;
t = mid/i;
if (mid%i == 0 && (t == (t & -t))) return false;
}
}
return false;
}
} | S*********2
发帖数: 172 | | R*****i
发帖数: 2126 | 3 楼主你应该做一些数学分析啊。不能成为pair 的有以下特征. 譬如(min, max), 在max
大于3倍min的时候，做增减数字的游戏。最后max=3*min，就不是
pair，否则，一定是pair(也就是循环）。
由于pair的两个数是不分先后的，所以（max，min)也一样。 | Y**D
发帖数: 5 | 4 第一条，a * 2， 直到能等于 b
第二条，b - 每个a * 2， 直到等等于原始的a
所以公式就是a*2的（n-1）次方要等于b
数学挺奇妙的，不管第一条，还是第二条，都推出来公式是a*2的（n-1）次方等于b
挺有意思的，我特意注册了个账号来讨论下哈。。。
我也不知道对不对啊，试试看哈
算下1到100之间 a * 2的（n-1）次方到达的b都在100以下的
我感觉就可以了。。。 | c****p
发帖数: 6474 | 5 max/min之后有O1的算法知道结果是不是2的n次方。
【在 Y**D 的大作中提到】
: 第一条，a * 2， 直到能等于 b
: 第二条，b - 每个a * 2， 直到等等于原始的a
: 所以公式就是a*2的（n-1）次方要等于b
: 数学挺奇妙的，不管第一条，还是第二条，都推出来公式是a*2的（n-1）次方等于b
: 挺有意思的，我特意注册了个账号来讨论下哈。。。
: 我也不知道对不对啊，试试看哈
: 算下1到100之间 a * 2的（n-1）次方到达的b都在100以下的
: 我感觉就可以了。。。
| R*****i
发帖数: 2126 | 6 a,b有大小范围限制，所以要判断max加min是不是min的2^n倍，最多31次<<操作
。譬如（
3，1），（7，1），（15，1），（31，1）都不是pair。 | f****g
发帖数: 207 | 7 (a,b) -> (2*a, b-a) -> (2*(2*a),(b-a)-2*a) -> ... after k operations, get
(2^k*a,b-\sum_{i=0}^{k-1} 2^i * a)
but \sum_{i=0}^{k-1} 2^i = 2^k - 1
Thus, stopping rule is:
given a < b, 2^k * a = b - (2^k-1)*a
which basically says (2^{k+1} - 1 ) a = b.
simply put, test if b / a + 1 is power of 2
1) if yes, stop.
2) if no, keep changing
power of 2 in one line operation
return n&(n-1);
hope this helps | s*******g
发帖数: 170 | 8 通过double我们得出:b=a*2^n;
通过b decreased by a我们得出b-(a+a*2+...+a*2^(n-1)) = a =>
b = a + (a+2a+...+2^(n-1)a) = 2a+2a+...+2^(n-1)a = 2^n*a;
所以两条路径都得出b/a = 2^n
x = 2^a => x > 0 && (x&(x-1))
decrease
pair.
【在 S*********2 的大作中提到】
: Given an array with length at least 1 and not more than 100. write a
: function which returns total pair of (a, b) in the array. Any pair start
: looping till they are equal. when a < b, a double itself. then b decrease
: by a.
: Vice versa. For example, 1,4 -> 2, 3 ->4, 1 -> 3, 2 -> 1, 4 and so on.
: Therefore,(1,4)
: count for a pair. 3,5 -> 6,2 -> 4,4, stop at 4== 4. so (3,5) is not a pair.
: a, b < 2^30 -1.
: code总是TLE， 请问有效率的判断方法，谢谢！
: 下面是我的code总是超时
| e*******s
发帖数: 1979 | 9 我觉得这个题是这么做的
既然总共长度不会超过100, 那么总的pair数不会超过10000
以pair为node建图, 此图
1. 有不超过10000个node
2. 每个node只有一个out bound edge, 但是可能有多个inbound edge, 总edge数也不
会超过10000
对于任意一节点, 寻找此节点是否在一个环路之中, 并用hashset记录下环路上的所有
节点, 此环路上的节点都是答案之一
例如1,4 -> 2, 3 ->4, 1 -> 3, 2 -> 1, 4 每一个pair都是答案之一.
简单的说就是用一个hashset做dp, 事实上也可以用int[100][100]做dp
decrease
pair.
【在 S*********2 的大作中提到】
: Given an array with length at least 1 and not more than 100. write a
: function which returns total pair of (a, b) in the array. Any pair start
: looping till they are equal. when a < b, a double itself. then b decrease
: by a.
: Vice versa. For example, 1,4 -> 2, 3 ->4, 1 -> 3, 2 -> 1, 4 and so on.
: Therefore,(1,4)
: count for a pair. 3,5 -> 6,2 -> 4,4, stop at 4== 4. so (3,5) is not a pair.
: a, b < 2^30 -1.
: code总是TLE， 请问有效率的判断方法，谢谢！
: 下面是我的code总是超时
| e*******s
发帖数: 1979 | 10 话说你这个题在哪儿看的 怎么知道TLE了
decrease
pair.
【在 S*********2 的大作中提到】
: Given an array with length at least 1 and not more than 100. write a
: function which returns total pair of (a, b) in the array. Any pair start
: looping till they are equal. when a < b, a double itself. then b decrease
: by a.
: Vice versa. For example, 1,4 -> 2, 3 ->4, 1 -> 3, 2 -> 1, 4 and so on.
: Therefore,(1,4)
: count for a pair. 3,5 -> 6,2 -> 4,4, stop at 4== 4. so (3,5) is not a pair.
: a, b < 2^30 -1.
: code总是TLE， 请问有效率的判断方法，谢谢！
: 下面是我的code总是超时
| | | s*****p
发帖数: 30 | 11
3, 8 => 6, 5 => 1, 10 => 2, 9 => 4, 7 => 8, 3 => 5, 6 => 10, 1 => 9, 2 => 7,
4 => 3, 8
【在 s*******g 的大作中提到】
: 通过double我们得出:b=a*2^n;
: 通过b decreased by a我们得出b-(a+a*2+...+a*2^(n-1)) = a =>
: b = a + (a+2a+...+2^(n-1)a) = 2a+2a+...+2^(n-1)a = 2^n*a;
: 所以两条路径都得出b/a = 2^n
: x = 2^a => x > 0 && (x&(x-1))
:
: decrease
: pair.
| s*******g
发帖数: 170 | 12 多谢
7,
【在 s*****p 的大作中提到】
:
: 3, 8 => 6, 5 => 1, 10 => 2, 9 => 4, 7 => 8, 3 => 5, 6 => 10, 1 => 9, 2 => 7,
: 4 => 3, 8
| Y**D
发帖数: 5 | 13 看到11楼，发现自己对题目理解错了，原来a和b的位置是可以互换的。
所以，又开始思考了。。。
拿到数字，先算下最大公约数哈，
因为（1，4） 能互换，那（2，8），（3，12）肯定能互换，不过带个因子，大家换
然后，在互换的过程中，任何a, b能出现大于1的最大公约数，就可以cut掉了，因为他
能回到这个一对数字
我这是手动推出来的，还在想怎么证明
咱再试试哈，看行不行。。。 | r********k
发帖数: 258 | 14 remeber both a and b at each iteration during looping, after the new
iteration, if one of (new_a, new_b) occurs in the past or new_a == new_b,
then terminates the loop. The check which case occurs.
if you only remember each a at each iteration, it just doubles the time to
run. remeber both a and b will cut time by half. The termination rule uses
the fact that a + b = new_a + new_b. | e***l
发帖数: 3 | 15 1. Any pair (A, B) such that A B = 2^N is not repairable, they eventually
land on a pair of 2^(N-1). 可以用数学归纳法证明。
2. Any pair of (p*A, p*B) is not pairable either if (A,B) satisfy condition
1
3. All rest are pairable
bool ispairable(int a, int b)
{
// assuming both a, b positive
int s = a b;
while (!(s | e***l
发帖数: 3 | 16 我贴了几次code都不成功。这其实是道数学题。
算出两个数和的最大的奇数因子。如果两个数都是这个奇数因子的倍数，最后肯定会相
等。否则就是循环。
: 1. Any pair (A, B) such that A B = 2^N is not repairable, they
eventually
: land on a pair of 2^(N-1). 可以用数学归纳法证明。
: 2. Any pair of (p*A, p*B) is not pairable either if (A,B) satisfy
condition
: 1
: 3. All rest are pairable
: bool ispairable(int a, int b)
: {
: // assuming both a, b positive
: int s = a b;
: while (!(s
【在 e***l 的大作中提到】
: 1. Any pair (A, B) such that A B = 2^N is not repairable, they eventually
: land on a pair of 2^(N-1). 可以用数学归纳法证明。
: 2. Any pair of (p*A, p*B) is not pairable either if (A,B) satisfy condition
: 1
: 3. All rest are pairable
: bool ispairable(int a, int b)
: {
: // assuming both a, b positive
: int s = a b;
: while (!(s
| m***c
发帖数: 13 | 17 结论是a+b==2^n
设置c = (a+b)/2;
我们观察a/c
如果不能parable，就是在某一步的a符合条件a/c == 1
a_new = 2*a or b-a
其中b - a == (2*c-a)-a == 2*c-2*a
a_new/c = 2*a/c or 1-2*a/c
如果c含有2以外的因子，a/c永远不可能是整数。所以一定parable。
反过来如果c全部因子都是2，每一次操作a/c的分母减少2倍，a/c最终一定成为整数。 | l******n
发帖数: 9344 | 18 3,8的例子就否定了你的结论
c就不一定是个整数
【在 m***c 的大作中提到】
: 结论是a+b==2^n
: 设置c = (a+b)/2;
: 我们观察a/c
: 如果不能parable，就是在某一步的a符合条件a/c == 1
: a_new = 2*a or b-a
: 其中b - a == (2*c-a)-a == 2*c-2*a
: a_new/c = 2*a/c or 1-2*a/c
: 如果c含有2以外的因子，a/c永远不可能是整数。所以一定parable。
: 反过来如果c全部因子都是2，每一次操作a/c的分母减少2倍，a/c最终一定成为整数。
| s*****p
发帖数: 30 | 19 问了个朋友，我把他的答案写了一下， 大家可以看一下对不对
http://bit.ly/2hG3XY2 | r********k
发帖数: 258 | 20 This is a CS programming question. Any attempt to come up a math formula to
verify it directly is not a solution. I have already gave you an answer at
comment 14.
【在 s*****p 的大作中提到】
: 问了个朋友，我把他的答案写了一下， 大家可以看一下对不对
: http://bit.ly/2hG3XY2
| | | o********t
发帖数: 31 | 21 .....
to
【在 r********k 的大作中提到】
: This is a CS programming question. Any attempt to come up a math formula to
: verify it directly is not a solution. I have already gave you an answer at
: comment 14.
| i****t
发帖数: 61 | 22 Second this
to
【在 r********k 的大作中提到】
: This is a CS programming question. Any attempt to come up a math formula to
: verify it directly is not a solution. I have already gave you an answer at
: comment 14.
| b***e
发帖数: 1419 | 23 原题：
Given an array with length at least 1 and not more than 100. write a
function which returns total pair of (a, b) in the array. Any pair start
looping till they are equal. when a < b, a double itself. then b decrease
by a.
Vice versa. For example, 1,4 -> 2, 3 ->4, 1 -> 3, 2 -> 1, 4 and so on.
Therefore,(1,4)
count for a pair. 3,5 -> 6,2 -> 4,4, stop at 4== 4. so (3,5) is not a pair.
a, b < 2^30 -1.
解答：
Lemma 0: Assume a
pair.
Proof: By definition.
QED
Lemma 1: If a and b are both even, then (a,b) is a pair if and only if (a/2,
b/2) is a pair.
Proof: Obviously.
QED
Lemma 2: If a>0, b>0 and a + b is odd, then (a, b) is a pair.
Proof: The transformation from (a, b) to (2*a, b-a) does not change the sum
of the pair because 2*a+b-a = a+b. If a + b is odd, then you can never
split it evenly to ((a+b)/2, (a+b)/2). There is a finite number of tuples (
x, y) where x+y = a+b and x != y. So there must be a loop in the
transformation chain because it cannot continue forever. Also, it must loop
back to (a,b), because the transformation is invertible. In other words,
if (a1,b1) -> (c,d) and (a2,b2) -> (c,d), then a1=a2 and b1=b2.
QED
Lemma 3: if a+b = 2^n for some n, then (a, b) is not a pair.
Proof: We play an induction on n.
Base case: if n = 1, then a = 1 and b = 1. So (a,b) is not a pair.
Induction case: assume the statement of Lemma 3 holds for n = k-1, and a + b
= 2^k. We do a case study on the parity of a and b:
If a and b are both even, then a/2+b/2 = 2^(k-1). By induction, (a/2,b/2)
is not a pair. Then by Lemma 1, (a,b) is not a pair.
It cannot be the case that a and b is one even and the other odd, because a
+ b is even.
If a and b are both odd. Then a != b, because otherwise a + b has an odd
factor. Without losing generality, assume a (2*a, b-a).
Note that a+(b-a)/2 = a/2+b/2 = 2^(k-1). By induction, (a, (b-a)/2) is not
a pair. So by Lemma 1, (2*a, b-a) is not a pair. By Lemma 0, (a,b) is not
a pair.
QED
Lemma 4: if gcd(p,q) = 1 and p + q = m * 2^n, where m is odd and m > 1, then
(p,q) is a pair.
Proof: We play an induction on n.
Base case: if n = 0; then p+q = m. By Lemma 2, (p,q) is a pair.
Induction case: assume the statement of Lemma 4 holds for n = k-1, and p+q =
m*2^k, where gcd(p,q) = 1, m is odd and m > 1. We do a case study on the
parity of p and q:
It cannot be both p and q are even because gcd(p,q)=1.
It cannot be p and q are one even and the other odd, because p+q is even (
due to k>0)
It can only be the case that both p and q are odd. Also note that p != q
because gcd(p,q)=1. Without losing generality, assume p (
2*p, q-p). Note that p+(q-p)/2 = p/2+q/2 = m*2^(k-1). Also, obviously, gcd
(p, (q-p)/2) = 1, because gcd(p,q)=1. Then by induction, (p, (q-p)/2) is
pair. Then by Lemma 1, (2*p, q-p) is a pair. Then by Lemma 0, (p, q) is a
pair.
QED
Theorem: Assume a>1, b>1, p = a/gcd(a,b), q = b/gcd(a,b). If p+q = 2^n for
some n > 1, then (a,b) is not a pair. Otherwise, (a,b) is a pair.
Proof: By Lemma 3 and Lemma 4.
QED
decrease
pair.
【在 S*********2 的大作中提到】
: Given an array with length at least 1 and not more than 100. write a
: function which returns total pair of (a, b) in the array. Any pair start
: looping till they are equal. when a < b, a double itself. then b decrease
: by a.
: Vice versa. For example, 1,4 -> 2, 3 ->4, 1 -> 3, 2 -> 1, 4 and so on.
: Therefore,(1,4)
: count for a pair. 3,5 -> 6,2 -> 4,4, stop at 4== 4. so (3,5) is not a pair.
: a, b < 2^30 -1.
: code总是TLE， 请问有效率的判断方法，谢谢！
: 下面是我的code总是超时
|
|
