I have to write a function which takes an integer array as input and it should return true if the array contains 1,2,3 or 4.

Conditions
1) The function should pass thru array only once.
2) Can use two local variable.
3) Preferably using bit manipulation.

Now suppose if the array has to be checked only for 1, 2 or 4 i have the solution.

Initialize the local var, say l_var = 0, i = 0(for array indexing)
Then pass thru the array using for loop and check
If
Array == 1 || Array == 2 || Array == 4
then
l_var = l_var | Array;

At the end of the loop check if l_var == 7
If its 7 return true;

Now I am not able to figure out how this can be done if 3 comes into picture. Since binary of 3 is 0011 (assuming 1 byte) I cannot use the above method.
Can anyone suggest some other solution.

3
Contributors
11
Replies
12
Views
12 Years
Discussion Span
Last Post by WolfPack

contains 1,2,3 or 4.

Should all 1,2,3 and 4 be in the array or is it enough to have only 1 out of those elements?

Use a switch inside for loop. Iterate through the array, if you find the value you are looking for, then, increment count inside that particular case else do nothing. In the end, check whether count contains 4 or not and return true or false accordingly.

Use a switch inside for loop. Iterate through the array, if you find the value you are looking for, then, increment count inside that particular case else do nothing. In the end, check whether count contains 4 or not and return true or false accordingly.

What if only 1 is present 5 times ??? Then also the count will be greater than 4

why can't you use

``````If
Array[i] == 1 || Array[i] == 2 || Array[i] == 3 || Array[i] == 4
then
l_var = l_var | (int)pow( 2, Array[i] );``````

At the end of the loop check if l_var == 15
If its 15 return true;

Should all 1,2,3 and 4 be in the array or is it enough to have only 1 out of those elements?

Array can contain 1,2,3 and 4 any number of times. Its not necessary that array has all the four. But if all the four are present then the function should return true otherwise false.

why can't you use

``````If
Array[i] == 1 || Array[i] == 2 || Array[i] == 3 || Array[i] == 4
then
l_var = l_var | (int)pow( 2, Array[i] );``````

At the end of the loop check if l_var == 15
If its 15 return true;

This seems to be a good sol. But should I check for 15 or 30 at the end

10
100
1000
10000
-----------
11110 -- 30 (dec)

Right??

Why 30?

Suppose in the array all 1, 2, 3 and 4 are present now after the operation
l_var = l_var | (int)pow( 2, Array );

= pow( 2, 1) | pow( 2, 2)| pow( 2, 3) | pow( 2, 4)
= 2 | 4 | 8 | 16
= 10 | 100 | 1000 | 10000 (all binary)
= 11110
= 30 (dec)

How did u got 15 ???

Suppose in the array all 1, 2, 3 and 4 are present now after the operation
l_var = l_var | (int)pow( 2, Array );

= pow( 2, 1) | pow( 2, 2)| pow( 2, 3) | pow( 2, 4)
= 2 | 4 | 8 | 16
= 10 | 100 | 1000 | 10000 (all binary)
= 11110
= 30 (dec)

How did u got 15 ???

Ach. Change it to

``l_var = l_var | (int)pow( 2, Array[i] - 1);``

so that the result becomes `1 | 2 | 4 | 8 = 15` use code tags next time.

``[LEFT]l_var = l_var | (int)pow( 2, Array[i]);[/LEFT]``

What is the problem with this if I am making check for 30?????

No problem for now. You will lose the checkable range by one number if you later decide to check for more. If you do the - 1, the powers start from 1 , you can go from
1, 2, 4, 8, .... max limit
If you dont do the - 1 the powers start only from 2, you can go from
2, 4, 8, .... You are missing 1 checkable position.
So there is the problem of upgrading the solution. And usually in production code, you will find flags start from 1 and go up from there. Not from 2 to above.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.