Find centralized, trusted content and collaborate around the technologies you use most.
Learn more about CollectivesStack Internal
Knowledge at work
Bring the best of human thought and AI automation together at your work.
Explore Stack InternalHow about a simple O(n) solution, with O(n*log(n)n^2) space? (Uses the assumption that all bitwise operators work in O(1).)
Someone will probably comment that for any sufficiently large number, bitwise operations cannot be done in O(1). You'd be right. However, I'd conjecture that every solution that uses addition, subtraction, multiplication, or division (which cannot be done by shifting) would also have that problem.
How about a simple O(n) solution, with O(n*log(n)) space? (Uses the assumption that all bitwise operators work in O(1).)
How about a simple O(n) solution, with O(n^2) space? (Uses the assumption that all bitwise operators work in O(1).)
Someone will probably comment that for any sufficiently large number, bitwise operations cannot be done in O(1). You'd be right. However, I'd conjecture that every solution that uses addition, subtraction, multiplication, or division (which cannot be done by shifting) would also have that problem.
How about a simple O(n) solution, with O(n*log(n)) space? (Uses the assumption that all bitwise operators work in O(1).)
Keep in mind that no step in the above algorithm takes longer than O(n). ^_^
I didn't really try optimizing the algorithmcode below, but it is compilable C# code that seems to work.
How about a simple O(n) solution, with O(n*log(n)) space?
I didn't really try optimizing the algorithm.
How about a simple O(n) solution, with O(n*log(n)) space? (Uses the assumption that all bitwise operators work in O(1).)
Keep in mind that no step in the above algorithm takes longer than O(n). ^_^
I didn't really try optimizing the code below, but it is compilable C# code that seems to work.
How about a simple O(n) solution, with O(n*log(n)) space?
The algorithm basically works in four stages:
Stage 1: For each bit in your original number, find out how far away the ones are, but consider only one direction. (I considered all the bits in the direction of the least significant bit.)
Stage 2: Reverse the order of the bits in the input;
Stage 3: Re-run step 1 on the reversed input.
Stage 4: Compare the results from Stage 1 and Stage 3. If any bits are equally spaced above AND below we must have a hit.
As an added benefit, this algorithm will find ALL equally spaced ones from EVERY number. So for example if you get a result of "0x0005" then there are equally spaced ones at BOTH 1 and 3 units away
I didn't really try optimizing the algorithm.
using System; namespace ThreeNumbers { class Program { const int uint32Length = 32; static void Main(string[] args) { Console.Write("Please enter your integer: "); uint input = UInt32.Parse(Console.ReadLine()); uint[] distancesLower = Distances(input); uint[] distancesHigher = Distances(Reverse(input)); PrintHits(input, distancesLower, distancesHigher); } /// <summary> /// Returns an array showing how far the ones away from each bit in the input. Only /// considers ones at lower signifcant bits. Index 0 represents the least significant bit /// in the input. Index 1 represents the second least significant bit in the input and so /// on. If a one is 3 away from the bit in question, then the third least significant bit /// of the value will be sit. /// /// As programed this algorithm needs: O(n) time, and O(n*log(n)) space. /// (Where n is the number of bits in the input.) /// </summary> public static uint[] Distances(uint input) { uint[] distanceToOnes = new uint[uint32Length]; uint result = 0; //Sets how far each bit is from other ones. Going in the direction of LSB to MSB for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex) { distanceToOnes[arrayIndex] = result; result <<= 1; if ((input & bitIndex) != 0) { result |= 1; } } return distanceToOnes; } /// <summary> /// Reverses the bits in the input. /// /// As programmed this algorithm needs O(n) time and O(n) space. /// (Where n is the number of bits in the input.) /// </summary> /// <param name="input"></param> /// <returns></returns> public static uint Reverse(uint input) { uint reversedInput = 0; for (uint bitIndex = 1; bitIndex != 0; bitIndex <<= 1) { reversedInput <<= 1; reversedInput |= (uint)((input & bitIndex) != 0 ? 1 : 0); } return reversedInput; } /// <summary> /// Goes through each bit in the input, to check if there are any bits equally far away in /// the distancesLower and distancesHigher /// </summary> public static void PrintHits(uint input, uint[] distancesLower, uint[] distancesHigher) { const int offset = uint32Length - 1; for (uint bitIndex = 1, arrayIndex = 0; bitIndex != 0; bitIndex <<= 1, ++arrayIndex) { //hits checks if any bits are equally spaced away from our current value bool isBitSet = (input & bitIndex) != 0; uint hits = distancesLower[arrayIndex] & distancesHigher[offset - arrayIndex]; if (isBitSet && (hits != 0)) { Console.WriteLine(String.Format("The {0}-th LSB has hits 0x{1:x4} away", arrayIndex + 1, hits)); } } } } }