# Blending problem solving with software development

1. Naive solution
`/*Approach — 1. decimal to binary conversion operation & store each bit in vector2. reverse vector to get the original binary representation of number back3. traverse each bit and store inverted bits in another vector4. binary to decimal conversion operation to get the complement of number*/int findComplement(int num) {      if(num == 0) return 1; //edgecase      vector<int> bits; //overhead 1 =: there is no need for extra space      while(num){        bits.push_back(num % 2);         num /= 2;     }          reverse(bits.begin(), bits.end()); //overhead 2 =: O(n) operation     //for(auto i : bits)cout<<i<<” “;     vector<int> complement; //overhead 3 =: there is no need for “more” extra space     for(auto i : bits){          if(i == 0) complement.push_back(1); //overhead 4 =: Another O(n) operation         else complement.push_back(0);     }      //cout<<”\n”;     //for(auto i : complement)cout<<i<<” “;      int sz = complement.size()- 1;     int complement_no = 0;      for(int i=sz; i>=0; i — ){         int expr = (complement[i] * pow(2, (sz- i)));         complement_no += expr;     }     //cout<<complement_no<<”\n”;    return complement_no;}`
`int findComplement(int num) {           if(num==0) return 1; //edgecase    vector<int>v; //overhead    //use of and operation and bitwise shifts makes this code little faster   while(num) {     v.push_back(num&1 ? 0:1);      num>>=1;   }  long long sum=0, cnt=0;  for(const auto i:v) {     sum += i*pow(2,cnt);     cnt++;  }  //cout<<sum<<"\n";  return sum;}`
`/*Approach -Find all set bits and calculate xor of set bits with number to get complement.Let, number ^ complement ==> (A)We know that ==> number ^ complement = set_bits number ^ (A) = number ^ set_bits (Xoring with number on both sides)0 ^ complement = number ^ set_bits (number xored with self equals 0)Hence, complement = number ^ set_bits.*/int findComplement(int num) {           if(!num) return 1; //edgecase   int set_bits = pow(2,0);   for(int i=1; set_bits<num; i++) set_bits += pow(2,i);   return num xor set_bits;}`
1. Usually its difficult to get intuition of last solution at first glance in the interview process. So the average solution is something that works ~okayish~ if you are facing the same problem in interview. The interviewers aren’t just looking for smart solutions; they are looking for well-written solutions. If you code something really smart but you are unable to explain it to your interviewers, all the smartness behind solution is futile.
2. Usually you start with brute-force and work towards optimising your solution. When asked about optimisation aspects, “yes”, the interviewers are looking for something better from your solution/approach alike the smart solution. (FAANG’s, MSFT and other product-based firms want this!)
3. Alongside problem-solving, system design, scalability, test-driven development and clean-code practices is something what recruiters are looking within you. Everything coupled above is makes a computer programmer the “real software engineer”

--

--