Problem Statement is given as,
Find all subarray index ranges in given Array with set bit sum equal to X
Given an array arr (1-based indexing) of length N and an integer X, the task is to find and print all index ranges having a set bit sum equal to X in the array.
Examples:
Input: A[] = {1 4 3 5 7}, X = 4
Output: (1, 3), (3, 4)
Explanation: In the above array subarray having set bit sum equal to X (= 4).
Starting from index 1 to 3. {1 4 3} = (001) + (100) + (011) = 4 and
other one is from 3 to 4 {3, 5} = (011) + (101) = 4.
Input: arr[] = {5, 3, 0, 4, 10}, X = 7
Output: (1 5)
Answer:
def countSetBit(arr, n):
c = 0
for i in range(n):
x = arr[i]
while (x):
l = x % 10
if (x & 1):
c += 1
x = x // 2
arr[i] = c
c = 0
def PrintIndex(arr, N, X, v):
i,j,currSum = 0,0,arr[0]
while (j < N and i < N):
if (currSum == X):
v.append(i + 1)
v.append(j + 1)
j += 1
if(j<N):
currSum += arr[j]
elif (currSum < X):
j += 1
if(j<N):
currSum += arr[j]
else:
currSum -= arr[i]
i += 1
# Driver code
v = [1, 4, 3, 5, 7]
X = 4
N = len(v)
countSetBit(v, N)
ans = []
PrintIndex(v, N, X, ans)
for i in range(0,len(ans) – 1,2):
print(f”({ans[i]} {ans[i + 1]})”,end=” “)