Find all subarray index ranges in given Array with set bit sum equal to XGiven 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. - MCQ Village

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.

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=” “)

Leave a comment

%d bloggers like this: