Count remaining array elements after reversing binary representation of each arr...
source link: https://www.geeksforgeeks.org/count-remaining-array-elements-after-reversing-binary-representation-of-each-array-element/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Count remaining array elements after reversing binary representation of each array element
- Last Updated : 31 May, 2022
Given an array arr[] consisting of N positive integers, the task is to modify every array element by reversing them binary representation and count the number of elements in the modified array that were also present in the original array.
Examples:
Input: arr[] = {2, 4, 5, 20, 16}
Output: 2
Explanation:
2 -> (10)2 -> (1) 2 -> 1 i.e. not present in the original array
4 -> (100 )2 -> (1 )2 -> 1 i.e. not present in the original array
5 -> (101 )2 -> (101 )2 -> 5 i.e. present in the original array
20 -> (10100)2 -> (101)2 -> 5 i.e. present in the original array
16 -> (10000)2 -> (1)2 -> 1 i.e. not present in the original arrayInput: arr[] = {1, 30, 3, 8, 12}
Output: 4
Approach: Follow the steps below to solve the problem:
- Initialize a variable, say count, to store the required count, a vector, say V, to store the reversed bits of each array element, and a Map to store the array elements in the original array.
- Traverse the given array arr[] and perform the following steps:
- Store the number formed by reversing each bit of binary representation of element arr[i] in the vector V.
- Mark the presence of the current element arr[i] in the Map.
- Traverse the vector V, and if any element present in the vector is also present in the Map, then increment count by 1.
- After completing the above steps, print the value of the count as the result.
Below is the implementation of the above approach:
- Python3
- Javascript
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to reverse the binary // representation of a number int findReverse( int N) { int rev = 0; // Traverse bits of N // from the right while (N > 0) { // Bitwise left // shift 'rev' by 1 rev <<= 1; // If current bit is '1' if (N & 1 == 1) rev ^= 1; // Bitwise right // shift N by 1 N >>= 1; } // Required number return rev; } // Function to count elements from the // original array that are also present // in the array formed by reversing the // binary representation of each element void countElements( int arr[], int N) { // Stores the reversed num vector< int > ans; // Iterate from [0, N] for ( int i = 0; i < N; i++) { ans.push_back(findReverse(arr[i])); } // Stores the presence of integer unordered_map< int , int > cnt; for ( int i = 0; i < N; i++) { cnt[arr[i]] = 1; } // Stores count of elements // present in original array int count = 0; // Traverse the array for ( auto i : ans) { // If current number is present if (cnt[i]) count++; } // Print the answer cout << count << endl; } // Driver Code int main() { int arr[] = { 1, 30, 3, 8, 12 }; int N = sizeof (arr) / sizeof (arr[0]); countElements(arr, N); return 0; } |
4
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(N), as we are using extra space for the map cnt.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK