Solution:
def count_bitwise_and_zero(nums: List[int]) -> int:
def get_set_bit_indices(x: int) -> List[int]:
"""Return indices of set bits in x"""
pow_2 = 1
exponent = 0
set_bits = []
while pow_2 <= x:
if pow_2 & x != 0:
set_bits.append(exponent)
exponent += 1
pow_2 *= 2
return set_bits
def is_bitwise_and_zero(window_length: int, bit_counts: Dict[int, int]) -> bool:
return all(value < window_length for value in bit_counts.values())
n = len(nums)
total_subarray_count = n * (n + 1) // 2
nonzero_subarray_count = 0
window_bit_counts = Counter()
"""At every iteration start, [left_idx, right_idx] is the longest subarray
ending at right_idx whose bitwise AND is nonzero."""
left_idx = 0
for right_idx, right_element in enumerate(nums):
if right_element == 0:
window_bit_counts.clear()
left_idx = right_idx + 1
continue
window_bit_counts += Counter(get_set_bit_indices(right_element))
while (left_idx < right_idx
and is_bitwise_and_zero(right_idx - left_idx + 1, window_bit_counts)):
window_bit_counts -= Counter(get_set_bit_indices(nums[left_idx]))
left_idx += 1
nonzero_subarray_count += (right_idx - left_idx + 1)
return total_subarray_count - nonzero_subarray_count
Solution : array AR of size N
perfect_sum(arr, s, result) :
x = [0]*len(arr)
j = len(arr) – 1
while (s > 0) :
x[j] = s % 2
s = s // 2
j -= 1
sum = 0
for i in range(len(arr)) :
if (x[i] == 1) :
sum += arr[i]
if (sum == result) :
print(“{“,end=””);
for i in range(len(arr)) :
if (x[i] == 1) :
print(arr[i],end= “, “);
print(“}, “,end=””)
def print_subset(arr, K) :
x = pow(2, len(arr))
for i in range(1, x):
perfect_sum(arr, i, K)
# Driver code
arr = [ ]
n = int(input(“Enter length of array : “))
s=int(input(“Enter sum : “))
for i in range(n):
ele=int(input(“Enter element : “))
arr.append(ele)
print_subset(arr, s)
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)
Solution :
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=" ")
Soluion 1:
def findXor(arr,n):
# Calculate xor of
# all the elements
xoR = 0;
for i in range (0, n ) :
xoR = xoR ^ arr[i]
# Return twice of
# xor value
return xoR * 2
# Driver code
arr = [ 1, 5, 6 ]
n = len(arr)
print(findXor(arr, n))
Solution 2:
def findXorSum(arr, n):
# variable to store the final Sum
Sum = 0
# multiplier
mul = 1
for i in range(30):
c_odd = 0
odd = 0
for j in range(n):
if ((arr[j] & (1 << i)) > 0):
odd = (~odd)
if (odd):
c_odd += 1
for j in range(n):
Sum += (mul * c_odd)
if ((arr[j] & (1 << i)) > 0):
c_odd = (n - j - c_odd)
mul *= 2
return Sum
arr = [3, 8, 13]
n = len(arr)
print(findXorSum(arr, n))
#include<iostream>
#include<unordered_map>
#include<string>
#include<math.h>
using namespace std;
int ans(string s){
unordered_map map;
for(int i =0; i map[s[i]]){
}}
return val; }
int main() {
string s;
cin>>s;
cout<< ans(s);
return 0; }
val = map[s[i]];
key = map[s[i]];
C++
Solution :
def findMax(arr, n):
large, index = 0, 0
for i in range(n):
if arr[i] > large:
large = arr[i]
index = i
# return the index of the maximum element
return index
def countSteps(arr, n):
index = findMax(arr, n)
steps = 1
while index != 0:
index = findMax(arr, index)
steps += 1
return steps
if __name__ == "__main__":
arr = [2, 5, 8, 24, 4, 11, 6, 1, 15, 10]
n = len(arr)
print("Steps Taken:", countSteps(arr, n))
Solution :
def findValue(arr, n):
a = []
b = []
for i in range(n):
a.append(arr[i] + i)
b.append(arr[i] - i)
x = a[0]
y = a[0]
for i in range(n):
if (a[i] > x):
x = a[i]
if (a[i] < y):
y = a[i]
ans1 = (x - y)
x = b[0]
y = b[0]
for i in range(n):
if (b[i] > x):
x = b[i]
if (b[i] < y):
y = b[i]
ans2 = (x - y)
return max(ans1, ans2)
if __name__ == '__main__':
arr = [1, 2, 3, 1]
n = len(arr)
print(findValue(arr, n))
Solution :
def getMaxToys(n,arr,money):
L,H=0,n-1
while(L<=H):
if(sum(arr[L:H+1])<=money):
break
else:
if arr[L]>arr[H]:
L+=1
else:
H-=1
return (H-L+1)
n=int(input())
arr=[]
for i in range(n):
arr.append(int(input()))
money=int(input())
print(getMaxToys(n,arr,money))
max = 4
# Recursive function to find the
# required number of ways
def countWays(index, cnt, dp, n, m, k):
# When all positions are filled
if (index == n) :
# If adjacent pairs are exactly K
if (cnt == k):
return 1
else:
return 0
# If already calculated
if (dp[index][cnt] != -1):
return dp[index][cnt]
ans = 0
# Next position filled with same color
ans += countWays(index + 1, cnt, dp, n, m, k)
# Next position filled with different color
# So there can be m-1 different colors
ans += (m - 1) * countWays(index + 1,
cnt + 1, dp, n, m, k)
dp[index][cnt] = ans
return dp[index][cnt]
# Driver Code
if __name__ == "__main__":
n=3
m=3
k=2
dp = [[-1 for x in range(n + 1)]
for y in range(max)]
print(m * countWays(1, 0, dp, n, m, k))
array AR of size N
perfect_sum(arr, s, result) :
x = [0]*len(arr)
j = len(arr) – 1
while (s > 0) :
x[j] = s % 2
s = s // 2
j -= 1
sum = 0
for i in range(len(arr)) :
if (x[i] == 1) :
sum += arr[i]
if (sum == result) :
print(“{“,end=””);
for i in range(len(arr)) :
if (x[i] == 1) :
print(arr[i],end= “, “);
print(“}, “,end=””)
def print_subset(arr, K) :
x = pow(2, len(arr))
for i in range(1, x):
perfect_sum(arr, i, K)
# Driver code
arr = [ ]
n = int(input(“Enter length of array : “))
s=int(input(“Enter sum : “))
for i in range(n):
ele=int(input(“Enter element : “))
arr.append(ele)
print_subset(arr, s)
Python
