Abhishek
BAN USERpublic static void main(String[] args) {
int[] a = {9,5,7,2,4,8,5,9,1,5};
int[] b = {9,1,1,1,2,3,8,5,9,1};
add(a,b);
}
static void add(int[] x, int[] y){
int xLength = x.length;
int yLength = y.length;
int zLength = Math.max(xLength, yLength)+1;
int[] z = new int[zLength];
int k = 0;
for (int i=1;i<=zLength;i++){
if(xLength-i<0 && yLength-i>=0){
z[zLength-i] = (y[yLength-i]+k)%10;
k = (y[yLength-i]+k)/10;
}
else if(yLength-i<0 && xLength-i>=0){
z[zLength-i] = (x[xLength-i]+k)%10;
k = (x[xLength-i]+k)/10;
}
else if(yLength-i<0 && xLength-i<0){
z[zLength-i] = k;
}
else if(yLength-i>=0 && xLength-i>=0){
z[zLength-i] = (x[xLength-i]+y[yLength-i]+k)%10;
k = (x[xLength-i]+y[yLength-i]+k)/10;
}
}
for (int i=0;i<zLength;i++){
System.out.print(z[i]);
}
System.out.println();
}
Nice solution.
Though, did you not miss a few printf's:
void print(char a[],int i)
{
if(a[i]=='\0')
{
printf("%s\n");
}
if(a[i]=='?')
{
a[i]='0';
printf("0");
print(a,i+1);
a[i]='1';
printf("1");
print(a,i+1);
}
else{
if(a[i]=='0'){printf("0");}
else{printf("1");}
print(a,i+1);
}
}
Step 1: Sort the array. Time: O(n.lgn).
Step 2: Create another array (in same sorted order) but eliminating all repetitions. Time: Theta(n). Memory: O(n).
Step 3: Create pairs and store in a 2D array. Say the first element is at index 'k' in the given array. This will be paired with all elements from 'k+1' to 'n' in the given aray and stored at an appropriate index in 2D array. Do this for k=1 to n. Time: O(n^2). Memory: O(n^2). Note that all pairs are in themselves sorted and the 2D array will have all possible combinations of pairs.
Step 4: Extend the same logic to create all 3-member subsets. Use the larger number's index (element at (x,1) in 2D array) to create all three-member subsets ( If the larger value is at index k in the given array, use from indices 'k+1' to 'n' to create triplets). Time: O(n^3), Memory: O(n^3). Note: All triplets will be sorted and would exhaust all possible combinations out of the given set of size n.
The same can be extended to any number of desired elements in subsets, in polynomial time.
JAVA code. I have not gone through all the above replies. Sorry, if a similar code is already posted.
public static void main(String[] args) {
long n = Long.parseLong(args[0]);
double num = 0;
double pos = 1;
while(pos<n){
num++;
pos = pos + (Math.floor(Math.log10(num))+1);
}
long y = (long)((pos-n)+1);
// System.out.println(""+(long)num+", "+y);
long num_long = (long)num;
String num_str = Long.toString(num_long);
long digit = (num_long%((long)(Math.pow(10,y))))/(((long)Math.pow(10,y-1)));
System.out.println(""+digit);
}
Speaking generally, would that reduce the solution to O(log n)? As far as I see, that will be O(n/k), where k=size of each fragment, which is essentially O(n). Though it will definitely fasten the calculation.
- Abhishek October 25, 2013For this particular case: assuming an int is 32-bit and we use a 8-bit table, that should be 4 steps, which is actually better than log 32 (=5).
Also, the elements of that table would need to have three values. (a) max no. of consecutive 0's in that element (within two 1s), (b) the number of consecutive 0s from left until the first 1 is encountered, (c) he number of consecutive 0s from right until the first 1 is encountered. The program would need to add the current (b) with previous (c) and compare that against (a) and the max so far(another variable). And, this doesn't handle the edge cases where only one 1 or zero 1 present in a fragment.