optimization - Sum of Hamming Distances -


I started preparing for an interview and came into the problem:

  • The integers An array is given
  • Now calculate the distance of all pairs of joints in the array in your binary representation.

Example: 

  given {1,2,3} or {001010011} (3 bit to simplify Used) result = HD (001010) + HD (001011) + HD (010,011) = 2 + 1 + 1 = 4;

With purely dead force solutions, I know that I can use here, here's the personal count of humming distance:

< Pre> int hemming_distance (unsigned x, unsigned y) {int dist; Unsigned wall; Dist = 0; Val = x ^ y; // Calculate the number of XOS / set bits (Wall! = 0) {// is a bit set, so increase the count and clear bit ++; Val & amp; = VAL - 1; } // Return the number of differentiated bits; }

What is the best way to solve this problem?

You can consider different bit-positions, this will give you 32 (or some other number) Gives easy problems, where you have to calculate the sum of all pairs of humming holes, except now it is more than 1-bit number.

1-bit number is their XOR.

And now it has become the easiest case of the problem - it's already split up per bit.

Therefore repeat the answer to that question, calculate a bit position, number of 0 and the number of 1, multiply those people to get the contribution of this bit position Yoga for all bit positions. Make it easier than the problem, because the weight of every problem is 1 in this problem.


Comments

Post a Comment

Popular posts from this blog

python - Overriding the save method in Django ModelForm -

I'm having trouble overriding a ModelForm save method. I get this error I'm: Exception type: TypeErier Exception Value: Save () found an unexpected keyword argument 'committed' My intentions include a form 3 fields Submit several values ​​for, then create an object for each combination of those areas, and to save each object file models.py class collarsult type (models.Model): id = model. AutoField (db_column = 'icontact_result_code_type_id', primary_key = true) callResult = models.ForeignKey ( 'CallResult', db_column = 'icontact_result_code_id') campaign = models.ForeignKey ( 'campaign', db_column = 'icampaign_id') CALLTYPE = models.ForeignKey ( 'CALLTYPE', db_column = 'icall_type_id') agent = models.BooleanField (db_column = 'bagent', default = true) teamLeader = models.BooleanField (db_column = 'bTeamLeader', default = true) active = models.BooleanField (db_column = Django.form...
Read more

html - CSS autoheight, but fit content to height of div -

I have a div in which there are three children- div in the left and middle div: float: left while true: float: true because it is my layout Actually will spoil, I've used ClearFix Hack: .cf {zoom: 1; }. Cf: First,. Cf: {content: ""; Display: Table; }. Cf: After {clear: both; } It still works, but I want to be the right div an indicator. So it should fill 100% of the parent unit of height. How can I complete this? PS is the full code: & Lt; / Div & gt; & Lt; Div class = "mobile_content" & gt; & Lt; H5 & gt; {{Data.titel}} & lt; / H5> & Lt; Table & gt; & Lt; TR & gt; & Lt; Th & gt; Komponist: & lt; / Th & gt; & Lt; TD & gt; {{Data.komponist}} & lt; / TD & gt; & Lt; / TR & gt; & Lt; TR & gt; & Lt; Th & gt; Instrument: & lt; / Th & gt; & Lt; TD & gt; {{Data.instrumente}} & lt; / TD & gt; & Lt; / TR & gt;...
Read more

qt - How to prevent QAudioInput from automatically boosting the master volume to 100%? -

I have been trying to use Qt5 multimedia to record audio with QAudioInput, however, when I see If QAudioInput is started, it increases the master volume of my sound device to 100%. How can I prevent QAudioInput from changing the master volume? My current development platform is Linux with PalsAdio (with flat audio disabled). How can I use QAudioInput : QAudioDeviceInfo device_info = QAudioDeviceInfo :: defaultInputDevice (); QAudio format format; Format.setSampleRate (44100); Format.setChannelCount (1); Format.setSampleSize (16); Format.setCodec ("Audio / PCM"); Format.setSampleType (QAudioFormat :: SignedInt); Format.setByteOrder (QAudioFormat :: LittleEndian); Std :: cout & lt; & Lt; Device_info.deviceName (). ToUtf8 (). ConstData () & lt; & Lt; Std :: endl; QAudioInput * default_device = new QAudioInput (device_info, format); QIODevice * default_io_device = default_device-> Start (); a QAudioInput.setVolume () method is not you I ...
Read more