Categories: MSDN / DotNet / Java / Scripts / Linux / PHP Ask - La ask - La Answer

an array problem (plz, help out) ......

hi,

I have a range of number between 1-101 ... the second thing i have is an array of capacity 100 (i.e on less than range i have)...

The problem is : if i fill array with no. from the range randomly without any repeatition..... how can i find the left integer in range

plz, don't iterate through the array or any other recursive looping stuff.
[377 byte] By [yeshendra] at [2007-11-11 8:48:42]
# 1 Re: an array problem (plz, help out) ......
if i fill array with no. from the range randomly without any repeatition..... how can i find the left integer in range

what do you mean by that?
you fill the array with random non repreating nos. that's clear.
are the numbers somehow sorted, or do you iterate through the array and set any random number into the actual array place?
and what is the "left integer in range"? the smallest number in the array?
could you post your code to fill the array?
graviton at 2007-11-11 22:34:25 >
# 2 Re: an array problem (plz, help out) ......
thanx for your concern ... here is the description of problem

The sequence is an example =>

STEP:1
List of nos : {1,2,3,.....,101} ; arr[] = new arr[100]

STEP:2
List of nos : {1,2,3,4,6,7...,101} ; arr[0]=5

STEP:3
List of nos : {1,2,3,.,72,74..,101} ; arr[1]=73

STEP: n-1
List of nos : {88,20} ; arr[98]= 50

STEP: n
List of nos : {88} ; arr[99]= 20

Now Given is i) Range{1-101}
ii) arr[] with nos populated as above (i.e randomly)

what is the best way to find out the no. missing in the array with minimum no. of steps required and effecient toooo......



what do you mean by that?
you fill the array with random non repreating nos. that's clear.
are the numbers somehow sorted, or do you iterate through the array and set any random number into the actual array place?
and what is the "left integer in range"? the smallest number in the array?
could you post your code to fill the array?
yeshendra at 2007-11-11 22:35:19 >
# 3 Re: an array problem (plz, help out) ......
ok, i understand, that you randomly put numbers from your list to an array.
this can be done through the following code

import java.util.Random;

public class Randomly {

/**
* @param args
*/
public static void main(String[] args) {
// initialize list

int [] listOfNos = new int[101];
int [] unusedNoPositionsInList = new int[101];
for (int i=0; i<=100; i++){
listOfNos[i] = i+1;
unusedNoPositionsInList[i] = i;
}
// System.out.println("list of nos: "+toString(listOfNos));

// prepare random selector
Random RND = new Random(System.currentTimeMillis());

int [] arr = new int[100];
int noPositionInUnusedNoPositionsInList;
int nextFreePositionInArr = 0;
int lastUnusedNoPosition;
while (nextFreePositionInArr<100){
lastUnusedNoPosition = 100-nextFreePositionInArr;
System.out.println("nextFreePositionInArr: "+nextFreePositionInArr);
System.out.println("lastUnusedNoPosition: "+(lastUnusedNoPosition));
System.out.println("list of nos: "+toString(listOfNos, unusedNoPositionsInList, lastUnusedNoPosition));
System.out.println("unusedNoPositionsInList: "+toString(unusedNoPositionsInList, lastUnusedNoPosition));
noPositionInUnusedNoPositionsInList = RND.nextInt(lastUnusedNoPosition);
System.out.println("noPositionInUnusedNoPositionsInList(rnd): "+noPositionInUnusedNoPositionsInList);
arr[nextFreePositionInArr] = listOfNos[unusedNoPositionsInList[noPositionInUnusedNoPositionsInList]];
System.out.println("no: "+arr[nextFreePositionInArr]);
if (unusedNoPositionsInList[noPositionInUnusedNoPositionsInList]!=lastUnusedNoPosition){
System.out.println("moving index");
unusedNoPositionsInList[noPositionInUnusedNoPositionsInList]=unusedNoPositionsInList[lastUnusedNoPosition];
System.out.println("unusedNoPositionsInList: "+toString(unusedNoPositionsInList, lastUnusedNoPosition));
}
nextFreePositionInArr++;
System.out.println("list of nos: "+toString(listOfNos, unusedNoPositionsInList, lastUnusedNoPosition-1));
System.out.println("arr: "+toString(arr, nextFreePositionInArr));
System.out.println("---");
}
System.out.println("finish");
System.out.println("list of nos: "+toString(listOfNos, unusedNoPositionsInList, 1));
System.out.println("unusedNoPositionsInList: "+toString(unusedNoPositionsInList, 1));
}

public static final String toString(int [] listOfNos, int [] unusedIndices, int len){
final StringBuffer sb = new StringBuffer(300);
for (int i=0; i<len; i++){
sb.append(listOfNos[unusedIndices[i]]);
if (i<len-1) sb.append(", ");
}
return sb.toString();
}

public static final String toString(int [] array){
return toString(array, array.length);
}

public static final String toString(int [] array, int len){
final StringBuffer sb = new StringBuffer(300);
int maxIndex = Math.min(len, array.length);
for (int i=0; i<maxIndex; i++){
sb.append(array[i]);
if (i<maxIndex-1) sb.append(", ");
}
return sb.toString();
}
}

but what i still dont understand is, what "no. missing in the array with minimum no. " means. can you show it in the example you provided?

by the way:
STEP: n-1
List of nos : {88,20} ; arr[98]= 50
should be
STEP: n-1
List of nos : {20,88} ; arr[98]= 50
graviton at 2007-11-11 22:36:23 >
# 4 Re: an array problem (plz, help out) ......
You must either check what is left in the list or what is missing in the array. If you store the array values at their index position offset one (e.g. a[n]=n+1), then the left value will stand out as a vacant slot (provided that you initialize the array w. say the minimum int value, Integer.MIN_VALUE). But...you will have to loop the array once to find it.
sjalle at 2007-11-11 22:37:23 >
# 5 Re: an array problem (plz, help out) ......
thanx, graviton & sjalle

by the way graviton here my code for the same:

import java.util.Random;

public class RandomNumbers {
public static void main(String args[]){
Random r = new Random(154785654);
int filled = 0;
int arr[] = new int[101];
int no=0;

for(;filled<100;
r = new Random(System.currentTimeMillis()*5)){
no = r.nextInt(101)+1;
filled += (arr[no-1]==0)?1:0;
arr[no-1] += ((arr[no-1]==0)?1:0);
}
// THE ISSUE:
for(int i=0;i<arr.length;i++) {
System.out.println("arr["+i+"]:"+arr[i]);
}
System.out.println("done");
}
}

Now the issue is after getting the 'arr' what is the best way to find out the missing number (beside checking for '0' in array), or is it the only way to find out the no

thanx

You must either check what is left in the list or what is missing in the array. If you store the array values at their index position offset one (e.g. a[n]=n+1), then the left value will stand out as a vacant slot (provided that you initialize the array w. say the minimum int value, Integer.MIN_VALUE). But...you will have to loop the array once to find it.
yeshendra at 2007-11-11 22:38:27 >
# 6 Re: an array problem (plz, help out) ......
as in your example, after the programm finished, you should have sthg like
STEP: n
List of nos : {88} ; arr[99]= 20

is the 88 the number you're looking for?
graviton at 2007-11-11 22:39:20 >