Problem

Submissions

Hints & solutions

Discuss

NINJA'S COMPLEMENT

Easy

0/40

Average time to solve is 20m

Contributed by

4 upvotes

Asked in companies

Problem statement

Everyday ninja sees a number in his dream but he doesn’t realize the meaning of that number. Somehow ninja manages to get the secret of his number. He comes to know that if he converts that number into binary and takes its complement and again converts it into decimal type he will get a lottery winning number of ‘Chit fund’ lottery.

But ninja is not good at maths so he is very sad about how he will get that lottery number from his dream’s number. So help our ninja in getting that lottery number.

Your task is to convert the given number into its binary form then take its complement ( Complement of a binary number is the value obtained by swapping all the bits i.e if ‘1’ is present you swap it with ‘0’ and vice versa ), then again convert it into its decimal representation.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a single integer ‘N’ denoting the given number.

Output Format:

For each test case, return the number after doing its complement.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 10 ^ 6

Time Limit: 1 sec

Sample Input 1:

2
4
6

Sample Output 1:

3
1

Explanation for sample input 1:

Test Case 1:
For the first test case, the given number is ‘4’ so its binary representation is ‘1 0 0’ after taking its complement it looks like ‘0 1 1’.  So now converting it into decimal we get ‘3’ so it’s our final answer.

Test Case 2:
For the first test case, the given number is ‘6’ so its binary representation is ‘1 1 0’ after taking its complement it looks like ‘0 0 1’.  So now converting it into decimal we get ‘1’ so it’s our final answer.

Sample Input 2:

1
9

Sample Output 2:

Explanation of sample input 2:

Test Case 1:
For the first test case, the given number is ‘9’ so its binary representation is ‘1 0 0 1’ after taking its complement it looks like ‘0 1 1 0’.  So now converting it into decimal we get ‘6’ so it’s our final answer.

Hint 1

Hint 2

Can you convert a number from binary to decimal and vice versa?

Approaches (2)

Approach 1

Approach 2

Brute Approach

The idea here is to divide the number by ‘2’ as for converting a number from decimal to binary we need to divide it by ‘2’ while dividing we can think of taking complement as if we get remainder ‘1’ we can store it as ‘0’ and if we get ‘0’ we can store it as ‘1’.

Algorithm:

Firstly we declare a variable ‘ANS’ which is used to store the final answer, ‘P’ is used to take the complement, and ‘K’ is used as a multiplier to convert binary number again into decimal where ‘ans’ is initialized with ‘0’ and ‘K’ with ‘1’
Now we start iterating using a while loop which runs until our number is greater than ‘0’.
In every iteration we check
- If the remainder is ‘0’ on dividing the number by ‘2’ we assign ‘P’ the value as ‘1’.
- Else we assign value to ‘P’ as ‘0’.
Now we increase the ‘ANS += P * K'. In every iteration, we multiply the ‘K’ by ‘2’ and divided the ‘N’ by ‘2’.
After the while loop, we return ‘ANS’.

Time Complexity

O(log(N) ), where ‘N’ represents the given number.

As we are running the while loop up to that number but in every iteration, we are dividing the ‘N’ by ‘2’ so the overall complexity of this loop becomes O(log(N) ).

Space Complexity

O(1).

As no extra space is required.

(100% EXP penalty)

NINJA'S COMPLEMENT

The Jester

Interview problems

Brute Force wae

#include <bits/stdc++.h>

int ninjaComplement(int n)

{

int ans=0,r,k=2,i=0;

if(n==0)

{

return 1;

}

while(n>0)

{

r=n%2;

if(r==0)

r=1;

else

r=0;

n=n/2;

ans=ans+r*pow(k,i);

i++;

}

return ans;

}

41 views

0 replies

0 upvotes

Sameer Kumar Singh

Interview problems

easy solution in cpp

#include <bits/stdc++.h>

int ninjaComplement(int n)

{

int m=n;

int mask =0;

if (n == 0) {

return 1;

}

while(m!=0)

{

mask = (mask << 1) | 1;

m =m>>1;

}

int ans=(~n)&mask;

return ans;

// Write your code here.

}

78 views

0 replies

0 upvotes

Ayush Bhatt

Interview problems

easy approach using bit manipulation

#include <bits/stdc++.h> int ninjaComplement(int n) { // Write your code here. int m=n; int mask=0; if(n==0){ return 1; } while(m!=0){ mask=(mask<<1)|1; m=m>>1; } int ans=(~n)&mask; return ans; }