leetcode

commit 3be481987589516e81b9b589226088d7a54113e5
parent 35f44b85d9a7704500d2675747bb426254fcd7d1
Author: Jack Sangdahl <jack@pngu.org>
Date:   Mon, 19 Jan 2026 22:12:53 -0700

3314. construct the minimum bitwse array 1

Diffstat:
A
construct_min_bitwise_arr1.c
 | 
45
+++++++++++++++++++++++++++++++++++++++++++++
A
construct_min_bitwise_arr1.py
 | 
31
+++++++++++++++++++++++++++++++

2 files changed, 76 insertions(+), 0 deletions(-)
diff --git a/construct_min_bitwise_arr1.c b/construct_min_bitwise_arr1.c
@@ -0,0 +1,45 @@
+// 3314. Construct the Minimum Bitwise Array I
+#include "leetcode.h"
+
+/*
+ * you are given an array 'nums' consisting of 'n' prime integers. you need to
+ * construct an array 'ans' of length 'n' such that for each index 'i', the
+ * bitwise or of 'ans[i]' and 'ans[i + 1]' is equal to 'nums[i]'. additionally,
+ * you must minimize each value 'ans[i]' in the resulting array. if it is not
+ * possible to find such a value for 'ans[i]' that satisfies the condition, then
+ * set 'ans[i] = -1'.
+ */
+
+int *minBitwiseArray(int *nums, int numsSize, int *returnSize) {
+  int *ans = (int *)malloc(numsSize * sizeof(int));
+  *returnSize = numsSize;
+  for (int i = 0; i < numsSize; ++i) {
+    int x = nums[i], v = 1;
+    bool found = false;
+    while (v < x) {
+      if ((v | (v + 1)) == x) {
+        ans[i] = v;
+        found = true;
+        break;
+      }
+      ++v;
+    }
+    if (!found)
+      ans[i] = -1;
+  }
+  return ans;
+}
+
+int main() {
+  int n1[] = {2, 3, 5, 7}, n2[] = {11, 13, 31};
+  int rs1, *mba1 = minBitwiseArray(n1, ARRAY_SIZE(n1), &rs1);
+  int rs2, *mba2 = minBitwiseArray(n2, ARRAY_SIZE(n2), &rs2);
+  for (int i = 0; i < rs1; i++)
+    printf("%d ", mba1[i]); // expect: -1 1 4 3
+  printf("\n");
+  for (int i = 0; i < rs2; i++)
+    printf("%d ", mba2[i]); // expect: 9 12 15
+  printf("\n");
+  free(mba1);
+  free(mba2);
+}
diff --git a/construct_min_bitwise_arr1.py b/construct_min_bitwise_arr1.py
@@ -0,0 +1,31 @@
+# 3314. Construct the Minimum Bitwise Array I
+
+"""
+you are given an array 'nums' consisting of 'n' prime integers. you need to
+construct an array 'ans' of length 'n' such that for each index 'i', the
+bitwise or of 'ans[i]' and 'ans[i + 1]' is equal to 'nums[i]'. additionally,
+you must minimize each value 'ans[i]' in the resulting array. if it is not
+possible to find such a value for 'ans[i]' that satisfies the condition, then
+set 'ans[i] = -1'.
+"""
+
+
+class Solution(object):
+    def minBitwiseArray(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: List[int]
+        """
+        ans = []
+        for i in nums:
+            if i & 1:
+                ans.append(i & -(((i + 1) & -i) >> 1))
+            else:
+                ans.append(-1)
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.minBitwiseArray(nums=[2, 3, 5, 7]))
+    print(obj.minBitwiseArray(nums=[11, 13, 31]))