2
\$\begingroup\$

Example 1
input:3
output:0011
Example 2
input : 15
output: 1111

in the below example code 15 is input.
I have taken 8 4 2 1 as array for Binary coded decimal numbering
this code is working as expected however i want to know how can i improve or optimize on this.

    static void Main(string[] args)
    {
        int[] arr = { 8, 4, 2, 1 };
        int num = 15;
        int[] carr = new int[arr.Length];
        Context.Print(arr,num,ref carr);
        Console.WriteLine(string.Join(' ',carr));
    }
    static void Print(int[] arr,int num,ref int[] carr)
    {
        bool two = false;
        if (arr[0 % arr.Length] + arr[0 + 1 % arr.Length] + arr[0 + 2 % arr.Length] + arr[0 + 3 % arr.Length] == num)
        {
            carr[0 % arr.Length] = 1;
            carr[0 + 1 % arr.Length] = 1;
            carr[0 + 2 % arr.Length] = 1;
            carr[0 + 3 % arr.Length] = 1;
            two = true;
            return;
        }
        for (int i=0 ; i < arr.Length ; i++)
        {
                if (arr[i % arr.Length] == num)
                {
                    carr[i % arr.Length] = 1;
                    two = true;
                    break;
                }
            for (int j = (i + 1); j < arr.Length; j++)
                if (arr[i % arr.Length] + arr[(j) % arr.Length] == num)
                {
                    carr[i % arr.Length] = 1;
                    carr[(j) % arr.Length] = 1;
                    two = true;
                    break;
                }
                else if ((arr[i % arr.Length] + arr[(j) % arr.Length] + arr[(j + 1) % arr.Length] == num))
                {
                    carr[i % arr.Length] = 1;
                    carr[(j) % arr.Length] = 1;
                    carr[(j + 1) % arr.Length] = 1;
                    two = true;
                    break;
                }
            
            if (two)
                break;
        }
    }
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Convert.ToString(num, 2).PadLeft('0', 4)? \$\endgroup\$
    – aepot
    Jul 6 at 19:57
4
\$\begingroup\$

Code Analysis

if (arr[0 % arr.Length] + arr[0 + 1 % arr.Length] + arr[0 + 2 % arr.Length] + arr[0 + 3 % arr.Length] == num)

This is duplicate in a way because it considers subset of cases as special ones. Having them might save time but it will not be much.

use of two

The code is

two = true;
return;

The use of two really starts with after first if. So it at least needs to be declared and used after that first loop.

next block

for (int i = 0; i < arr.Length; i++)

The objective is to find if current bit being assigned to needs to 1 or 0. But, code tries to do it in substantially complex way. This complex mechanism would be needed if we were not considering actual values based on bits (8, 4, 2, 1). But since we are considering actual values code can be simplified (which is given below)

Unit tests We need to have a way to verify the output is what we expect. If it is not possible by actual unit test framework, code should have some way to automating it.

Performance testing The question mentions point about performance so it would be better to have some way to verifying in controlled fashion.

Modified Code

I managed to modify your code but I modified almost entirely. I am not sure if it is acceptable but I thought it was good exercise. Perhaps you can use it.

Compiled with VS 2019 community

Modified Method

        static void PrintFromChanged(int[] arr, int num, ref int[] carr, int[] carrRight = null)
        {

            for (int index = 0;index < arr.Length && 0 < num; ++index)
            {
                if (1 == (carr[index] = (num >= arr[index] ? 1 : 0)))
                {
                    num -= arr[index];
                }
            }
        }

Full Code

        static void Main(string[] args)
        {
            int[] arr = { 8, 4, 2, 1 };

            bool atLeastOneDidntMatch = false;
            for (int num = 0; num < 16; ++num)
            {
                int[] carr = new int[arr.Length];
                Program.PrintFromStackExchange(arr, num, ref carr);
                int[] carrChanged = new int[arr.Length];
                Program.PrintFromChanged(arr, num, ref carrChanged, carr);

                bool same = true;
                for (int i = 0; i < arr.Length; ++i)
                {
                    if (carr[i] != carrChanged[i])
                    {
                        int[] carrChanged2 = new int[arr.Length];
                        same = false;
                        break;
                    }
                }

                if (!same)
                {
                    Console.WriteLine(num + ": " + string.Join(" ", carr) + " : " + string.Join(" ", carrChanged));
                }
            }


            if (!atLeastOneDidntMatch && 1 == args.Length)
            {
                
                const long iterations = 1000000;
                System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();

                if ("1".Equals(args[0]))
                {
                    watch.Start();
                    for (long i = 0; i < iterations; ++i)
                    {
                        for (int num = 0; num < 16; ++num)
                        {
                            int[] carr = new int[arr.Length];
                            Program.PrintFromChanged(arr, num, ref carr);
                        }
                    }
                    watch.Stop();
                    long msModified = watch.ElapsedMilliseconds;
                    Console.WriteLine("16 million calls: Time Modified: " + msModified);
                }
                else
                {

                    watch.Start();
                    for (long i = 0; i < iterations; ++i)
                    {
                        for (int num = 0; num < 16; ++num)
                        {
                            int[] carr = new int[arr.Length];
                            Program.PrintFromStackExchange(arr, num, ref carr);
                        }
                    }
                    watch.Stop();
                    long msOriginal = watch.ElapsedMilliseconds;

                    Console.WriteLine("16 million calls: Time Modified: " + msOriginal);
                }
            }

        }

        static void PrintFromChanged(int[] arr, int num, ref int[] carr, int[] carrRight = null)
        {

            for (int index = 0;index < arr.Length && 0 < num; ++index)
            {
                if (1 == (carr[index] = (num >= arr[index] ? 1 : 0)))
                {
                    num -= arr[index];
                }
            }
        }


        static void PrintFromStackExchange(int[] arr, int num, ref int[] carr)
        {
            bool two = false;
            if (arr[0 % arr.Length] + arr[0 + 1 % arr.Length] + arr[0 + 2 % arr.Length] + arr[0 + 3 % arr.Length] == num)
            {
                carr[0 % arr.Length] = 1;
                carr[0 + 1 % arr.Length] = 1;
                carr[0 + 2 % arr.Length] = 1;
                carr[0 + 3 % arr.Length] = 1;
                two = true;
                return;
            }
            for (int i = 0; i < arr.Length; i++)
            {
                if (arr[i % arr.Length] == num)
                {
                    carr[i % arr.Length] = 1;
                    two = true;
                    break;
                }
                for (int j = (i + 1); j < arr.Length; j++)
                    if (arr[i % arr.Length] + arr[(j) % arr.Length] == num)
                    {
                        carr[i % arr.Length] = 1;
                        carr[(j) % arr.Length] = 1;
                        two = true;
                        break;
                    }
                    else if ((arr[i % arr.Length] + arr[(j) % arr.Length] + arr[(j + 1) % arr.Length] == num))
                    {
                        carr[i % arr.Length] = 1;
                        carr[(j) % arr.Length] = 1;
                        carr[(j + 1) % arr.Length] = 1;
                        two = true;
                        break;
                    }

                if (two)
                    break;
            }
        }

Performance

16 million calls: Time Original: 800 Modified: 286

16 million calls: Time Original: 836 Modified: 337

16 million calls: Time Original: 819 Modified: 251

16 million calls: Time Original: 862 Modified: 279

16 million calls: Time Original: 818 Modified: 281

16 million calls: Time Original: 762 Modified: 279

16 million calls: Time Original: 837 Modified: 316

16 million calls: Time Original: 947 Modified: 303

16 million calls: Time Original: 902 Modified: 282

16 million calls: Time Original: 837 Modified: 306

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Why left [i % arr.Length] everywhere? \$\endgroup\$
    – aepot
    Jul 7 at 16:26
1
\$\begingroup\$

I think your code is more complex than needed for this problem. I will start with your method signature:

static void Print(int[] arr,int num,ref int[] carr)

You will have to know a lot about your parameters: arr needs to be an array of powers of two and carr has to be an array of 0s. What happens if one calls this method and these two conditions are not fulfilled? I propose the following signature:

static int[] Print(int num, int length)

Instead of passing the result via a ref parameter (which is quite uncommon and should only be done if it is not possible in another way), I will use the return type. I also pass the length of the result (in your case 4) to make the method more flexible. Finally, I don't use the array of powers of two as an input, because this can be calculated by your method.

In the method, first I check if length is big enough to display the result:

if(num >= (1 << length))
{
    throw new ArgumentException(num + " is too big to be displayed in a binary output of length " + length);
}

The operation with binary shift operator << is equivalent to 2 to the power of length. If length is 4, the maximum number which can be displayed is 15. I throw an exception if the output array is too short to make sure, that the caller won't process wrong data.

Then, I create the result array:

int[] result = new int[length];

Then, I use a single loop to fill the array with the correct values:

for(int i = result.Length - 1; i >= 0; i--)
{
    int powerOfTwo = 1 << i;
    int index = result.Length - i - 1;
    result[index] = num / powerOfTwo;
    num -= result[index] * powerOfTwo;
}

The power of two is calculated via the bit-shift operator. Because the array has to be filled from the back, we need a new array index. Then the value in the result array is calculated.

The full code of your method is:

static int[] Print(int num, int length)
    {
        if(num >= (1 << length))
        {
            throw new ArgumentException(num + " is too big to be displayed in a binary output of length " + length);
        }
        int[] result = new int[length];
        for(int i = result.Length - 1; i >= 0; i--)
        {
            int powerOfTwo = 1 << i;
            int index = result.Length - i - 1;
            result[index] = num / powerOfTwo;
            num -= result[index] * powerOfTwo;
        }
        return result;
    }

Online demo: https://dotnetfiddle.net/HsqrnJ

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.