Flipkart Interview Question
SDE-2sCountry: India
Interview Type: In-Person
Nice solution.
To improve the performance we can traverse the inner loop in reverse order i.e.
for(int j=i;j>=1;--j)
and get the value of the current segment incrementally.
But integer overflows may still happen.
Nice solution.
To improve the performance we can traverse the inner loop in reverse order i.e.
for(int j=i;j>=1;--j)
and get the value of the current segment incrementally.
But integer overflows may still happen.
@Scott
I agree with the thought. You may need to check f[j-1] before taking it into account, what if f[j-1] is Integer.MAX_VALUE.
Code in python:
import math
def sliceIntoMultiplesOf5(s):
def isPowerOf5(s):
x = int(s, 2)
n = int(math.log2(x) / math.log2(5))
return 5 ** n == x
# initialize
n = len(s)
f = [-1] * n
# dp
for i in range(n):
if isPowerOf5(s[:i+1]):
f[i] = 1
continue
for j in range(i):
# pieces do not start with 0
if f[j] == -1 or s[j+1] == '0' or not isPowerOf5(s[j+1:i+1]):
continue
if f[i] == -1:
f[i] = f[j] + 1
else:
f[i] = min(f[i], f[j] + 1)
# result
return f[n-1]
# test case
strList = [
"101101101",
"1111101",
"110011011",
"1000101011",
"111011100110101100101110111"
]
for s in strList:
print(sliceIntoMultiplesOf5(s))
'''
The following code takes a binary number as input and prints the number
of chunks in the number which are divisible by 5.
'''
import sys
import math
def validateInput(inputStream):
isValid = True;
for x in inputStream:
if x != '0' and x != '1':
isValid = False;
break;
return isValid;
'''
For divisibility by 5, the number must end in 1010 or 101.
'''
def processInput(inputStream):
chunk = '';
chunksDivisibleBy5 = 0;
for x in inputStream:
chunk += x;
decimal = convertBinaryToDecimal(chunk);
if decimal is not None and decimal%5 == 0:
chunksDivisibleBy5 += 1;
chunk = '';
return chunksDivisibleBy5;
'''
Converts a binary number to its decimal counterpart.
'''
def convertBinaryToDecimal(inputStream):
length = len(inputStream);
decimal = 0;
for x in inputStream:
decimal += length * math.pow(int(x), length - 1);
return decimal;
def main():
input = sys.argv[1];
inputStream = list(input);
if (validateInput(inputStream)):
print 'Valid input';
chunksDivisibleBy5 = processInput(inputStream);
print chunksDivisibleBy5 if chunksDivisibleBy5 != 0 else -1;
else:
print 'Invalid input. The input should contain only 0s and 1s.';
if __name__ == '__main__':
main()
1) Consider int start = 0, curr = 0;
2) Traverse from left to right one letter at a time and and increment curr++ accordingly.
3) Validate whether the number formed from start to curr index is in power of 5 or not. If it is then increment k and also update start variable to curr+1 (start=curr+1)
Wow this seems to be an intimidating problem at first but if you think about it you just need to split once a power of five is found then look for another sets after that chunk and used memoization to recall when you already processed a previous chunk.
I used a hash set to know if a number is a power of 5.
I think there are better solutions but this is what I would came up with at the moment.
public int FindSplitsOfPowerOfFive(string S)
{
return CoreFindSplits(S, 0, S.Length, new Dictionary<string, int>());
}
private int CoreFindSplits(string S, int start, int end, Dictionary<string, int> memo)
{
string hash = start + "," + end;
if(memo.ContainsKey(hash))
{
return memo[hash];
}
var sorted = SortedDictionary<int, int>()
// Find all Powers of Five while parsing
long current = 0;
int min = -2;
for(int i = start, i < S.Length; i++)
{
current <<= 1;
current += S[i] =='1'?1:0;
if(IsPowerOfFive(current))
{
int sub = CoreFindSplits(S, i+1, end, memo);
if(sub != -1 && sub < min)
{
min = sub + 1;
}
}
}
memo.Add(hash, min);
return min;
}
private bool IsPowerOfFive(long number)
{
// Precalculated all powers of five for efficient lookup
const HashSet<long> powersOfFive = new HashSet<long>
{
5,
25,
125,
625,
3125,
15625,
78125,
390625,
1953125,
9765625,
48828125,
244140625,
1220703125,
6103515625,
30517578125,
152587890625,
762939453125,
3814697265625,
19073486328125,
95367431640625,
476837158203125,
2384185791015625,
11920928955078125,
59604644775390625,
298023223876953125,
1490116119384765625,
7450580596923828125
};
return powersOfFive.Contains(number);
}
#pragma GCC optimize "-O3"
#include <bits/stdc++.h>
#include <tr1/unordered_map>
using namespace std;
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ll long long int
#define llu unsigned long long int
#define I int
#define S string
#define D double
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define in(n) scanf("%lld",&n)
#define in2(a,b) scanf("%lld %lld",&a,&b)
#define in3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define out(a) printf("%lld\n",a)
#define inu(a) scanf("%lld",&a)
#define outu(a) printf("%llu",a)
#define outf(a) printf("%.9f\n", a);
#define mod 1000000007
#define inf 100000000000000
#define MM(a,x) memset(a,x,sizeof(a));
#define ALL(x) (x).begin(), (x).end()
#define UN(v) sort(ALL(v)), v.resize(unique(ALL(v))-v.begin())
#define fill(a,x) memset(a,x,sizeof(a))
#define MP make_pair
#define PB push_back
#define f first
#define s second
#define sz(v) v.size()
#define nl cout<<"\n"
#define MX1 100005
#define MX2 1000005
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<llu> vllu;
typedef vector<string> vs;
typedef vector<pll> vpll;
bool check(int i , string s , int k){
ll ans = 0;
for(int j = k ; j >= i ; j--)
ans = ans + ((s[j] - '0') * pow(2,k - j));
while(ans > 0){
if(ans % 5 == 0)
ans/=5;
else if(ans != 1)
return(false);
if(ans == 1)
return(true);
}
}
int main(){
fast;
// freopen("A-large-practice.in","r",stdin);
// freopen("output_file_name.out","w",stdout);
S s;
cin >> s;
ll k = sz(s)-1;
int i;
int count = 0;
while(k >= 0){
for(i = 0 ; i <= k ; i++){
bool p = check(i,s,k);
if(p){
count++;
k = --i;
break;
}
}
if(k < 0)
break;
}
cout << count << endl;
}
dynamic programming
f[i] = min (f[j -1] + 1, f[i])
- Scott June 16, 2015