leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

longest_square_streak_arr.c (1648B)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// 2501. Longest Square Streak in an Array
#include "leetcode.h"

/*
 * you are given an integer array 'nums'. a subsequence of 'nums' is called a
 * square streak if the length of the subsequence is at least 2 and after
 * sorting the subsequence, each element (except the first element) is the
 * square of the previous number. return the length of the longest square streak
 * in 'nums', or '-1' otherwise. a subsequence is an array that can be derived
 * from another array by deleting some or no elements without changing the order
 * of the remaining elements.
 */

int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }

bool search(long long *nums, int numsSize, long long target) {
  int l = 0, h = numsSize - 1;
  while (l <= h) {
    int m = l + (h - l) / 2;
    if (nums[m] == target)
      return true;
    if (nums[m] < target)
      l = m + 1;
    else
      h = m - 1;
  }
  return false;
}

int longestSquareStreak(int *nums, int numsSize) {
  qsort(nums, numsSize, sizeof(int), cmp);
  long long *stk = (long long *)malloc(numsSize * sizeof(long long));
  for (int i = 0; i < numsSize; ++i)
    stk[i] = nums[i];
  long long ans = -1;
  for (int i = 0; i < numsSize; ++i) {
    long long val = (long long)nums[i], cnt = 1;
    while (search(stk, numsSize, val * val)) {
      val *= val;
      cnt++;
    }
    if (cnt > 1 && ans < cnt)
      ans = cnt;
  }
  free(stk);
  return (int)ans;
}

int main() {
  int n1[] = {4, 3, 6, 16, 8, 2}, n2[] = {2, 3, 5, 6, 7};
  printf("%d\n", longestSquareStreak(n1, ARRAY_SIZE(n1))); // expect: 3
  printf("%d\n", longestSquareStreak(n2, ARRAY_SIZE(n2))); // expect: -1
}