Given an array with n elements. The task is to find the maximum number of contiguous array elements which have the same number of set bits.
Examples:
Input : arr[] = {14, 1, 2, 32, 12, 10}
Output : 3
Elements 1, 2, 32 have same number of set bits
and are contiguous.
Input : arr[] = {1, 6, 9, 15, 8}
Output : 2
Elements 6, 9 have same number of set bits.
Approach:
- Traverse the array from left to right and store the number of set bits of each element in a vector.
- Our task is reduced in finding the longest chain of same elements in this vector.
- Maintain two variables, current_count and max_count. Initialise both of them with 1.
- Traverse the vector and check if current element is same as previous element. If it is same, increment current_count. If it is not same, then reinitialize current_count with 1.
- At each step, max_count must be assigned maximum value between max_count and current_count.
- Final value of max_count is the answer.
Below is the implementation of the above approach:
C++
// C++ program to find the maximum number of// contiguous array elements with same// number of set bits#include <bits/stdc++.h>using namespace std;// Function to find maximum contiguous elements// with same set bitsint sameSetBits(int arr[], int n){ vector<int> v; // Insert number of set bits in each element // of the array to the vector // __builtin_popcount() function returns the number // of set bits in an integer in C++ for (int i = 0; i < n; i++) v.push_back(__builtin_popcount(arr[i])); int current_count = 1, max_count = 1; // Finding the maximum number of same // contiguous elements for (int i = 1; i < v.size(); i++) { if (v[i + 1] == v[i]) current_count++; else current_count = 1; max_count = max(max_count, current_count); } // return answer return max_count;}// Driver codeint main(){ int arr[] = { 9, 75, 14, 7, 13, 11 }; int n = sizeof(arr) / sizeof(arr[0]); cout << sameSetBits(arr, n); return 0;} |
Java
// Java program to find the maximum // number of contiguous array elements// with same number of set bitsimport java.io.*;import java.util.*;class GFG{ // Function to find maximum contiguous // elements with same set bits static int sameSetBits(int arr[], int n) { Vector<Integer> v = new Vector<>(); // Insert number of set bits in each element // of the array to the vector for (int i = 0; i < n; i++) { int count = Integer.bitCount(arr[i]); v.add(count); } int current_count = 1, max_count = 1; // Finding the maximum number of same // contiguous elements for (int i = 1; i < v.size()-1; i++) { if (v.get(i + 1) == v.get(i)) current_count++; else current_count = 1; max_count = Math.max(max_count, current_count); } // return answer return max_count; } // Driver code public static void main (String[] args) { int arr[] = { 9, 75, 14, 7, 13, 11 }; int n = arr.length; System.out.println(sameSetBits(arr, n)); }}// This code is contributed by Archana_kumari |
Python3
# Python 3 program to find the maximum # number of contiguous array elements # with same number of set bits# Function to find maximum contiguous# elements with same set bitsdef sameSetBits(arr, n): v = [] # Insert number of set bits in each # element of the array to the vector # function returns the number of set # bits in an integer for i in range(0, n, 1): v.append(bin(arr[i]).count('1')) current_count = 1 max_count = 1 # Finding the maximum number of same # contiguous elements for i in range(1, len(v) - 1, 1): if (v[i + 1] == v[i]): current_count += 1 else: current_count = 1 max_count = max(max_count, current_count) # return answer return max_count# Driver codeif __name__ == '__main__': arr = [9, 75, 14, 7, 13, 11] n = len(arr) print(sameSetBits(arr, n))# This code is contributed by# Surendra_Gangwar |
C#
// C# program to find the maximum // number of contiguous array elements // with same number of set bits using System;using System.Collections.Generic;class GFG { // Function to find maximum contiguous // elements with same set bits static int sameSetBits(int []arr, int n) { List<int> v = new List<int>(); // Insert number of set bits in each element // of the array to the vector for (int i = 0; i < n; i++) { int count = Bitcount(arr[i]); v.Add(count); } int current_count = 1, max_count = 1; // Finding the maximum number of same // contiguous elements for (int i = 1; i < v.Count-1; i++) { if (v[i + 1] == v[i]) current_count++; else current_count = 1; max_count = Math.Max(max_count, current_count); } // return answer return max_count; } static int Bitcount(int n) { int count = 0; while (n != 0) { count++; n &= (n - 1); } return count; } // Driver code public static void Main (String[] args) { int []arr = { 9, 75, 14, 7, 13, 11 }; int n = arr.Length; Console.WriteLine(sameSetBits(arr, n)); } } // This code has been contributed by 29AjayKumar |
Javascript
<script>// Javascript program to find the maximum number of// contiguous array elements with same// number of set bitsfunction Bitcount(n){ var count = 0; while (n != 0) { count++; n &= (n - 1); } return count;} // Function to find maximum contiguous elements// with same set bitsfunction sameSetBits(arr, n){ var v = []; // Insert number of set bits in each element // of the array to the vector // Bitcount function returns the number // of set bits in an integer in C++ for (var i = 0; i < n; i++) v.push(Bitcount(arr[i])); var current_count = 1, max_count = 1; // Finding the maximum number of same // contiguous elements for (var i = 1; i < v.length; i++) { if (v[i + 1] == v[i]) current_count++; else current_count = 1; max_count = Math.max(max_count, current_count); } // return answer return max_count;}// Driver codevar arr = [ 9, 75, 14, 7, 13, 11 ];var n = arr.length;document.write( sameSetBits(arr, n));</script> |
Output
4
Time Complexity: O(n), since __builtin_popcount has a maximum complexity of 32 for each int value.
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
