artakbegnazaryan
BAN USERGood answer. Here are versions to set, clear and flip n-th bit of m:
int set_nth_bit(const int m, const int n)
{
return m | (1 << n);
}
int clear_nth_bit(const int m, const int n)
{
return m & ~(1 << n);
}
int flip_nth_bit(const int m, const int n)
{
return m ^ (1 << n);
}
Yeah this was a great tutorial to understand this conversion.
I wrote a small program to convert the binary code into Gray code using iteration based on this tutorial if someone would be interested.
#include <iostream>
template <typename T>
void set_bit(T& value, size_t n)
{
value = value | (1 << n);
}
template <typename T>
bool is_bit_set(T value, size_t n)
{
return 0 == (value & (1 << n)) ? false : true;
}
template <typename T>
T binary_to_gray_iterative(T binary, size_t number_of_bits = 8 * sizeof(T))
{
T gray = T();
for (size_t i = 0; i < number_of_bits - 1; ++i) {
if (is_bit_set(binary, i) != is_bit_set(binary, i + 1)) {
set_bit(gray, i);
}
}
if (is_bit_set(binary, number_of_bits - 1)) {
set_bit(gray, number_of_bits - 1);
}
return gray;
}
template <typename T>
void print_binary_code(T element)
{
for (int i = 8 * sizeof(T) - 1; i >= 0; --i) {
std::cout << (0 == (element & (1 << i)) ? 0 : 1);
}
std::cout << std::endl;
}
int main (int argc, const char * argv[])
{
char binary = 0x7B;
print_binary_code(binary);
char gray = binary_to_gray_iterative(binary);
print_binary_code(gray);
return 0;
}
Working example using BST and modified insertion algorithm.
//
// main.cpp
// SmallerElementsOnRightSide
//
// Created by Artak Begnazaryan on 3/2/12.
//
#include <iostream>
struct Node {
int value;
Node* left;
Node* right;
size_t num_of_lefts;
Node(int val)
: value(val)
, left(0)
, right(0)
, num_of_lefts(0)
{
}
};
struct BST {
Node* root;
BST()
: root(0)
{
}
size_t insert_element(int value)
{
if (0 == root) {
root = new Node(value);
return 0;
}
size_t result = 0;
Node* runner = root;
while (0 != runner) {
if (runner->value < value) {
++result;
result += runner->num_of_lefts;
if (0 == runner->right) {
runner->right = new Node(value);
return result;
} else {
runner = runner->right;
}
} else {
++runner->num_of_lefts;
if (0 == runner->left) {
runner->left = new Node(value);
return result;
} else {
runner = runner->left;
}
}
}
return 0;
}
};
void smaller_elements_on_right_side(int array[], size_t size, size_t result[])
{
BST tree;
for (int i = (int)(size - 1); i >= 0; --i) {
result[i] = tree.insert_element(array[i]);
}
}
template <typename T>
void print_array(T array[], size_t size)
{
for (size_t i = 0; i < size; ++i) {
std::cout << array[i] << ' ';
}
std::cout << std::endl;
}
int main (int argc, const char * argv[])
{
const size_t size = 8;
int array[size] = {4, 12, 5, 6, 1, 34, 3, 2};
size_t result[size] = {0};
smaller_elements_on_right_side(array, size, result);
print_array(array, size);
print_array(result, size);
return 0;
}
This solution is partially correct. If we do nothing when go left then we're just ignoring them and they'll not appear in later calculations. This will result to wrong numbers, e.g. for the array in example [4, 12, 5, 6, 1, 34, 3, 2] we will get the result [2, 3, 2, 2, 0, 1, 0].
For the correct solution we need to keep the number of left subtree children also for each node (let's define it as num_of_lefts). So when for a given element we should go to left we should increment num_of_lefts for the parent node. Else if we should go to right we should both increment the counter and add the num_of_lefts (as we know for sure they'll also be less than the current element and their indexes are greater in the original array).
You can find my implementation in C++ in the page comments.
Here is the non-recursive implementation in C++.
void print_all_substrings_iterative(const std::string& str)
{
const size_t size = str.size();
for (size_t i = 1; i < std::pow(2.0, (double)size); ++i) {
for (size_t j = 0; j < size; ++j) {
if (i & (1 << j)) {
std::cout << str[j];
}
}
std::cout << ' ';
}
std::cout << std::endl;
}
Take an array of size (N - k) and fill it with the numbers not in the subset. Then just pick arr[rand() % (N - k)].
- artakbegnazaryan July 20, 2011
If O (logn) is not possible and we should find the answer in O (n) then we don't need all this stuff like preprocessing and binary search. We can just iterate the array from the beginning and stop as we hit a number which is greater than or equal to A. Something like this:
Please correct me if I'm wrong.
- artakbegnazaryan March 02, 2012