Blue Amethyst
Junior Member
Em thử sức thử phátCó bài này cho anh em thử
Đi siêu thị mua gạo, có 1 dãy các túi gạo với trọng lượng khác nhau. Bạn muốn mua 1 dãy perfect sao cho cứ túi này thì bằng bình phương trọng lượng túi trước. Tìm dãy dài nhất có thể
Ví dụ: Input: 3 9 2 4 16
Dãy nhiều các thím có thể mua dc là 2 4 16 -> output = 3
Ràng buộc: Input array size = n < 10^5
trọng lượng túi gạo < 10^6
Ko có link đâu, nên các thím tự tạo test case cho pass corner case nhé
Java:
[QUOTE]
private static int solve(int[] bags)
{
if (bags.length == 0)
{
return 0;
}
Set<Integer> set = new HashSet<>();
for (int bag : bags)
{
set.add(bag);
}
int max = 1;
for (int bag : bags)
{
int count = 1;
if (set.contains(bag))
{
set.remove(bag);
int weight = bag;
while (set.remove((int)Math.sqrt(weight)))
{
++count;
weight = (int)Math.sqrt(weight);
}
weight = bag;
while (set.remove((int)Math.pow(weight, 2)))
{
++count;
weight = (int)Math.pow(weight, 2);
}
max = Math.max(max, count);
}
}
return max;
}
Last edited by a moderator: