Cogoport Developer Hiring Challenge , January'18 | HackerEarth

Recently, I participated in programming contest : Cogoport Developer Hiring Challenge.
It has been months since I had participated in any kind of such programming contest (in HackerEarth or HackerRank or SPOJ). I needed to brush up my algorithmic concepts. My purpose was to solve all the questions so that I could get a chance to attend Cogoport interview. So with this in my mind, I logged in and started solving Cogoport developer hiring challenge on HackerEarth.

There were total 4 problems. Before, I jump into the the details, I must elaborate different tags associated with all these 4 problems. So here they are: string manipulation, palindrome, binary number.

To my embarrashment, I couldn't even solve one of them in the allotted time as I told you I had not brushed up my concepts. So, anyway, later, I solved them in my free time. I had tried two problems. So I am going to talk about those two. I will try to remember those two problems.

Problems:
1. You are given a binary number as a string, n. n has substrings. Find the number of all odd decimal representations of the substrings. Binary number will be assumed from left to right.

Input: First line contains integer, t, number of test cases. For each test case, string, n is given as               input.
Output: For each string n, print out number of all odd decimal representations of substrings.

[Note: There was a condition for len(n)]

Solution: Here is what I thought while solving this problem. If any odd number represented in binary,  then its binary number has 1 at its least significant position.
Example: binary(5)=101, binary(7)=1101. In 5, 7 cases, 1 is always at the end : least significant position. So using this simple knowledge, we are done.
Now let's take an example : n=1101
substrings of n: 1, 1, 0, 1, 11, 10, 01, 110, 101, 1101. Total=10 substrings.
Remember: binary number : from left to right as said in the problem statement.
1, 1, 1, 11, 10, 110, 101, 1101 are our solutions as they are odd decimal representation.
not 01 because left to right , that means , in 01 , least significant position has 0 and it makes it even decimal representation.

That's lot of things to digest. Anyway, think about this. Here is a C++ code for it.

#include <iostream>
using namespace std;
int utility(string b){
int n=b.length();
int s=0;
for(int i=0;i<n;i++){
if(b[i]=='1'){
int j=n-i;
s+=j;
}
}
return s;
}
int main(){
string b;
cin >> b;
cout << utility(b);
return 0;
}


2. Problem 2.

You are given two integer n and k. You need to find a special binary number of length n which satisfies palindrome condition. This binary number has to be created by concatenating binary string of length k.

Speical binary number has properties:
A. It must have at least 1 '0' and 1 '1'.
B. If there are more that one such special binary number, they you need to print the one which has highest number of zeros in it.

Input: First line contains an integer, t, number of test cases. Each test case line should have two input: n and k.

Output: print the special binary  number if found otherwise print "impossible".

example: n=8, k=5, special binary number=100101001
               n=10, k=6, special binary number=1001001001
               n=8, k=2, special binary number=impossible

Here is the code:

#include <iostream>
#include <map>
using namespace std;

map<string, int> repeat;
bool palindrome(string s){
int n=s.length();
int zero=0;
int found=1;
int j=0;
for(int i=0;i<n/2;i++){
if(s[i]!=s[n-j-1]){
found=0;
break;
}
if(s[i]=='0'){
zero=1;
}
j++;
}
if(found==0){
return false;
}else{
if(zero==1){
return true;
}else{
return false;
}
}
}

bool getBinary(int n, int k, string k1, int x){
if(x<k){
k1[x]='1';
}
string k2=k1;
string s="";
string prefix="";
int f=0;
while(true){

if(k1.length()>=n){
int i=0;
k1=prefix+k1;
s="";
while(i<k1.length()){
s+=k1[i];
                                             if(s.length()==n and s[0]=='1' and palindrome(s)){
cout << "ans s: " << s << endl;
return true;
}
if(repeat[s]==1){
return false;
}
if((s.length()==n and !palindrome(s)) or (s.length()==n and s[0]=='0')){
repeat[s]=1;
s="";
}
i++;
}
prefix=s;
k1="";
}else{
k1+=k2;
}
if(prefix==k2){
return false;
}

}
}
void utility(int n, int k){
string k1="1";
bool ans=false;
for(int i=0;i<k-1;i++){
k1+="0";
}
int found=0;
if(n==k and k1[0]=='1' and palindrome(k1) ){
cout << k1 << endl;
}else{

int j=k;
while(j>=1){
ans=getBinary(n, k, k1, j);
if(ans){
found=1;
break;
}
j--;
}
}
if(found==0){
cout << "impossible" << endl;
}
}
int main(){
int n, k;
cin >> n >> k;
utility(n, k);
return 0;
}


Please let me know if You had participated in this challenge or If you find anything wrong in this thread.
Cogoport developer hiring challenge