Problem
I tried solving the Hash Tables: Ice Cream Parlor question in javascript:
'use strict';
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', function() {
inputString = inputString.replace(/s*$/, '')
.split('n')
.map(str => str.replace(/s*$/, ''));
main();
});
function readLine() {
return inputString[currentLine++];
}
// Complete the whatFlavors function below.
function whatFlavors(cost, money) {
// Solution starts here
var dict1={};
var len=cost.length;
for(var i=0; i<len; i++) {
if (cost[i]<money) {
if(dict1[cost[i]] !== undefined)
{
if(Array.isArray(dict1[cost[i]]))
{
dict1[cost[i]].push(i);
}
else
{
dict1[cost[i]] = [dict1[cost[i]]];
dict1[cost[i]].push(i);
}
}
else
dict1[cost[i]] = i;
}
}
cost.sort(function(a,b) {return a-b});
for(var j=0; j<len; j++){
var left=0;
var right=len-1;
if(cost[j]<money){
var ser=money-cost[j];
while(left<right){
var mid=Math.floor((left+right)/2);
if(ser===cost[mid]){
var val1=cost[j];
var val2=cost[mid];
break;
}
if(ser<cost[mid]){
right = mid-1;
}
else{
left = mid+1;
}
}
if(val1 !== undefined && val2 !== undefined ){
break;
}
}
}
var index1;
var index2;
if (val1===val2) {
index1 = dict1[val1][0];
index2 = dict1[val2][1];
}
else{
index1 = dict1[val1];
index2 = dict1[val2];
}
if (index2 > index1) {
console.log(index1+1, index2+1);
}
else{
console.log(index2+1, index1+1);
}
// Solution ends here
}
function main() {
const t = parseInt(readLine(), 10);
for (let tItr = 0; tItr < t; tItr++) {
const money = parseInt(readLine(), 10);
const n = parseInt(readLine(), 10);
const cost = readLine().split(' ').map(costTemp => parseInt(costTemp, 10));
whatFlavors(cost, money);
}
}
It works for all inputs except when it is very large, for example when the input is very large for eg:
30733 39289
12352 19413
448 3955
74 75
12316 34744
2916 4669
1941 6571
2871 17443
34132 42603
1753 9623
7217 8111
3411 17665
3190 16653
1923 14237
6307 22944
10874 22052
967 21913
7562 7948
11038 36319
586 8260
338 1426
17083 37691
11944 15889
10347 13601
643 1653
18754 19595
9561 22822
22521 26308
114 1965
338 412
8423 9497
6371 33551
1292 3705
5634 9563
14043 14669
12566 39425
1149 2638
12664 12939
10217 29104
it simply throws Wrong Answer
, is there a better way to write the same script?
Solution
The error was because of a silly mistake, in the binary search, it should be while(left<=right)
:
'use strict';
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', function() {
inputString = inputString.replace(/s*$/, '')
.split('n')
.map(str => str.replace(/s*$/, ''));
main();
});
function readLine() {
return inputString[currentLine++];
}
// Complete the whatFlavors function below.
function whatFlavors(cost, money) {
// Solution starts here
var dict1={};
var len=cost.length;
for(var i=0; i<len; i++) {
if (cost[i]<money) {
if(dict1[cost[i]] !== undefined)
{
if(Array.isArray(dict1[cost[i]]))
{
dict1[cost[i]].push(i);
}
else
{
dict1[cost[i]] = [dict1[cost[i]]];
dict1[cost[i]].push(i);
}
}
else
dict1[cost[i]] = i;
}
}
cost.sort(function(a,b) {return a-b});
for(var j=0; j<len; j++){
var left=0;
var right=len-1;
if(cost[j]<money){
var ser=money-cost[j];
while(left<=right){
var mid=Math.floor((left+right)/2);
if(ser===cost[mid]){
var val1=cost[j];
var val2=cost[mid];
break;
}
if(ser<cost[mid]){
right = mid-1;
}
else{
left = mid+1;
}
}
if(val1 !== undefined && val2 !== undefined ){
break;
}
}
}
var index1;
var index2;
if (val1===val2) {
index1 = dict1[val1][0];
index2 = dict1[val2][1];
}
else{
index1 = dict1[val1];
index2 = dict1[val2];
}
if (index2 > index1) {
console.log(index1+1, index2+1);
}
else{
console.log(index2+1, index1+1);
}
// Solution ends here
}
function main() {
const t = parseInt(readLine(), 10);
for (let tItr = 0; tItr < t; tItr++) {
const money = parseInt(readLine(), 10);
const n = parseInt(readLine(), 10);
const cost = readLine().split(' ').map(costTemp => parseInt(costTemp, 10));
whatFlavors(cost, money);
}
}