Dada una array ordenada que consta de 0 y 1. El problema es encontrar el índice del primer ‘1’ en la array ordenada. Podría ser posible que la array consista en solo 0 o solo 1. Si los 1 no están presentes en la array, imprima «-1».
Ejemplos:
Input : arr[] = {0, 0, 0, 0, 0, 0, 1, 1, 1, 1}
Output : 6
The index of first 1 in the array is 6.
Input : arr[] = {0, 0, 0, 0}
Output : -1
1's are not present in the array.
Fuente: Preguntado en Amazon Entrevista
Enfoque ingenuo: recorra la array de izquierda a derecha y devuelva el índice del primer ‘1’. Si los 1 no están presentes en la array, imprima «-1»
Implementación:
C++
// C++ implementation to find the index of
// first '1' in a sorted array of 0's and 1's
#include <bits/stdc++.h>
using namespace std;
// function to find the index of first '1'
int indexOfFirstOne(int arr[], int n)
{
// traverse the array from left to right
for (int i = 0; i < n; i++)
// if true, then return i
if (arr[i] == 1)
return i;
// 1's are not present in the array
return -1;
}
// Driver program to test above
int main()
{
int arr[] = { 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << indexOfFirstOne(arr, n);
return 0;
}
Java
// Java program to find the index of
// first '1' in a sorted array of 0's and 1's
class GFG {
// function to find the index of first '1'
public static int indexOfFirstOne(int arr[], int n)
{
// traverse the array from left to right
for (int i = 0; i < n; i++)
// if true, then return i
if (arr[i] == 1)
return i;
// 1's are not present in the array
return -1;
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr[] = { 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 };
int n = arr.length;
System.out.println(indexOfFirstOne(arr, n));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 implementation to find # the index of first '1' in a # sorted array of 0's and 1's # function to find the index of first '1' def indexOfFirstOne(arr, n): # traverse the array from left to right for i in range(0, n): # if true, then return i if (arr[i] == 1): return i # 1's are not present in the array return -1 # Driver program to test above arr = [ 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 ] n = len(arr) ans = indexOfFirstOne(arr, n) print(ans) # This code is contributed by saloni1297
C#
// C# program to find the index of
// first '1' in a sorted array
// of 0's and 1's
using System;
class GFG
{
// function to find the index of first '1'
public static int indexOfFirstOne(int []arr, int n)
{
// traverse the array from left to right
for (int i = 0; i < n; i++)
// if true, then return i
if (arr[i] == 1)
return i;
// 1's are not present in the array
return -1;
}
// Driver program
public static void Main()
{
int []arr = { 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 };
int n = arr.Length;
Console.Write(indexOfFirstOne(arr, n));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP implementation to find the index of
// first '1' in a sorted array of 0's and 1's
// function to find the index of first '1'
function indexOfFirstOne($arr, $n)
{
// traverse the array from
// left to right
for ($i = 0; $i < $n; $i++)
// if true, then return i
if ($arr[$i] == 1)
return $i;
// 1's are not present
// in the array
return -1;
}
// Driver Code
$arr = array(0, 0, 0, 0, 0, 0, 1, 1, 1, 1);
$n = sizeof($arr) / sizeof($arr[0]);
echo indexOfFirstOne($arr, $n);
return 0;
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// Javascript implementation to find the index of
// first '1' in a sorted array of 0's and 1's
// function to find the index of first '1'
function indexOfFirstOne(arr, n)
{
// traverse the array from left to right
for (let i = 0; i < n; i++)
// if true, then return i
if (arr[i] == 1)
return i;
// 1's are not present in the array
return -1;
}
// Driver program to test above
let arr = [ 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 ];
let n = arr.length;
document.write(indexOfFirstOne(arr, n));
//This code is contributed by Mayank Tyagi
</script>
<script>
// Javascript implementation to find the index of
// first '1' in a sorted array of 0's and 1's
// function to find the index of first '1'
function indexOfFirstOne(arr, n)
{
// traverse the array from left to right
for (let i = 0; i < n; i++)
// if true, then return i
if (arr[i] == 1)
return i;
// 1's are not present in the array
return -1;
}
// Driver program to test above
let arr = [ 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 ];
let n = arr.length;
document.write(indexOfFirstOne(arr, n));
//This code is contributed by Mayank Tyagi
</script>
<script>
// Javascript implementation to find the index of
// first '1' in a sorted array of 0's and 1's
// function to find the index of first '1'
function indexOfFirstOne(arr, n)
{
// traverse the array from left to right
for (let i = 0; i < n; i++)
// if true, then return i
if (arr[i] == 1)
return i;
// 1's are not present in the array
return -1;
}
// Driver program to test above
let arr = [ 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 ];
let n = arr.length;
document.write(indexOfFirstOne(arr, n));
//This code is contributed by Mayank Tyagi
</script>
<script>
// Javascript implementation to find the index of
// first '1' in a sorted array of 0's and 1's
// function to find the index of first '1'
function indexOfFirstOne(arr, n)
{
// traverse the array from left to right
for (let i = 0; i < n; i++)
// if true, then return i
if (arr[i] == 1)
return i;
// 1's are not present in the array
return -1;
}
// Driver program to test above
let arr = [ 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 ];
let n = arr.length;
document.write(indexOfFirstOne(arr, n));
//This code is contributed by Mayank Tyagi
</script>
<script>
// Javascript implementation to find the index of
// first '1' in a sorted array of 0's and 1's
// function to find the index of first '1'
function indexOfFirstOne(arr, n)
{
// traverse the array from left to right
for (let i = 0; i < n; i++)
// if true, then return i
if (arr[i] == 1)
return i;
// 1's are not present in the array
return -1;
}
// Driver program to test above
let arr = [ 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 ];
let n = arr.length;
document.write(indexOfFirstOne(arr, n));
//This code is contributed by Mayank Tyagi
</script>
<script>
// Javascript implementation to find the index of
// first '1' in a sorted array of 0's and 1's
// function to find the index of first '1'
function indexOfFirstOne(arr, n)
{
// traverse the array from left to right
for (let i = 0; i < n; i++)
// if true, then return i
if (arr[i] == 1)
return i;
// 1's are not present in the array
return -1;
}
// Driver program to test above
let arr = [ 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 ];
let n = arr.length;
document.write(indexOfFirstOne(arr, n));
//This code is contributed by Mayank Tyagi
</script>
<script>
// Javascript implementation to find the index of
// first '1' in a sorted array of 0's and 1's
// function to find the index of first '1'
function indexOfFirstOne(arr, n)
{
// traverse the array from left to right
for (let i = 0; i < n; i++)
// if true, then return i
if (arr[i] == 1)
return i;
// 1's are not present in the array
return -1;
}
// Driver program to test above
let arr = [ 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 ];
let n = arr.length;
document.write(indexOfFirstOne(arr, n));
//This code is contributed by Mayank Tyagi
</script>
<script>
// Javascript implementation to find the index of
// first '1' in a sorted array of 0's and 1's
// function to find the index of first '1'
function indexOfFirstOne(arr, n)
{
// traverse the array from left to right
for (let i = 0; i < n; i++)
// if true, then return i
if (arr[i] == 1)
return i;
// 1's are not present in the array
return -1;
}
// Driver program to test above
let arr = [ 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 ];
let n = arr.length;
document.write(indexOfFirstOne(arr, n));
//This code is contributed by Mayank Tyagi
</script>
<script>
// Javascript implementation to find the index of
// first '1' in a sorted array of 0's and 1's
// function to find the index of first '1'
function indexOfFirstOne(arr, n)
{
// traverse the array from left to right
for (let i = 0; i < n; i++)
// if true, then return i
if (arr[i] == 1)
return i;
// 1's are not present in the array
return -1;
}
// Driver program to test above
let arr = [ 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 ];
let n = arr.length;
document.write(indexOfFirstOne(arr, n));
//This code is contributed by Mayank Tyagi
</script>
<script>
// Javascript implementation to find the index of
// first '1' in a sorted array of 0's and 1's
// function to find the index of first '1'
function indexOfFirstOne(arr, n)
{
// traverse the array from left to right
for (let i = 0; i < n; i++)
// if true, then return i
if (arr[i] == 1)
return i;
// 1's are not present in the array
return -1;
}
// Driver program to test above
let arr = [ 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 ];
let n = arr.length;
document.write(indexOfFirstOne(arr, n));
//This code is contributed by Mayank Tyagi
</script>
Producción
6
Complejidad de tiempo: O(n)
Enfoque eficiente (búsqueda binaria): use la técnica de búsqueda binaria en la array ordenada, para encontrar el índice del primer ‘1’.
Implementación:
C++
// C++ implementation to find the index of first
// '1' in a sorted array of 0's and 1's
#include <bits/stdc++.h>
using namespace std;
// function to find the index of first '1'
// binary search technique is applied
int indexOfFirstOne(int arr[], int low, int high)
{
while (low <= high) {
int mid = (low + high) / 2;
// if true, then 'mid' is the index of first '1'
if (arr[mid] == 1 && (mid == 0 || arr[mid - 1] == 0))
return mid;
// first '1' lies to the left of 'mid'
else if (arr[mid] == 1)
high = mid - 1;
// first '1' lies to the right of 'mid'
else
low = mid + 1;
}
// 1's are not present in the array
return -1;
}
// Driver program to test above
int main()
{
int arr[] = { 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << indexOfFirstOne(arr, 0, n - 1);
return 0;
}
Java
// Java program to find the index of
// first '1' in a sorted array of 0's and 1's
class GFG {
// function to find the index of first '1'
// binary search technique is applied
public static int indexOfFirstOne(int arr[], int low,
int high)
{
while (low <= high) {
int mid = (low + high) / 2;
// if true, then 'mid' is the index of first '1'
if (arr[mid] == 1 && (mid == 0 || arr[mid - 1]
== 0))
return mid;
// first '1' lies to the left of 'mid'
else if (arr[mid] == 1)
high = mid - 1;
// first '1' lies to the right of 'mid'
else
low = mid + 1;
}
// 1's are not present in the array
return -1;
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr[] = { 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 };
int n = arr.length;
System.out.println(indexOfFirstOne(arr, 0,
n - 1));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 implementation to find # the index of first '1' in a # sorted array of 0's and 1's # function to find the index of first '1' # binary search technique is applied def indexOfFirstOne( arr, low, high): while (low <= high): mid = int((low + high) / 2) # if true, then 'mid' is the index of first '1' if (arr[mid] == 1 and (mid == 0 or arr[mid - 1] == 0)): return mid # first '1' lies to the left of 'mid' elif (arr[mid] == 1): high = mid - 1 # first '1' lies to the right of 'mid' else: low = mid + 1 # 1's are not present in the array return -1; # Driver program to test above arr = [0, 0, 0, 0, 0, 0, 1, 1, 1, 1 ] n = len(arr) ans = indexOfFirstOne(arr, 0, n - 1) print (ans) # This code is contributed by saloni1297
C#
// C# program to find the index of
// first '1' in a sorted array of 0's and 1's
using System;
class GFG
{
// function to find the index of first '1'
// binary search technique is applied
public static int indexOfFirstOne(int []arr, int low,
int high)
{
while (low <= high) {
int mid = (low + high) / 2;
// if true, then 'mid' is the index of first '1'
if (arr[mid] == 1 && (mid == 0 || arr[mid - 1]
== 0))
return mid;
// first '1' lies to the left of 'mid'
else if (arr[mid] == 1)
high = mid - 1;
// first '1' lies to the right of 'mid'
else
low = mid + 1;
}
// 1's are not present in the array
return -1;
}
// Driver program
public static void Main()
{
int []arr = { 0, 0, 0, 0, 0, 0, 1, 1, 1, 1 };
int n = arr.Length;
Console.Write(indexOfFirstOne(arr, 0, n - 1));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP implementation to find
// the index of first '1' in
// a sorted array of 0's and 1's
// function to find the index
// of first '1' binary search
// technique is applied
function indexOfFirstOne($arr,
$low,
$high)
{
while ($low <= $high)
{
$mid = ceil($low +
$high) / 2;
// if true, then 'mid' is
// the index of first '1'
if ($arr[$mid] == 1 and
($mid == 0 or
$arr[$mid - 1] == 0))
return $mid;
// first '1' lies to the
// left of 'mid'
else if ($arr[$mid] == 1)
$high = $mid - 1;
// first '1' lies to
// the right of 'mid'
else
$low = $mid + 1;
}
// 1's are not present
// in the array
return -1;
}
// Driver Code
$arr = array(0, 0, 0, 0, 0,
0, 1, 1, 1, 1);
$n = count($arr);
echo indexOfFirstOne($arr, 0, $n - 1);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript implementation to find the index of first
// '1' in a sorted array of 0's and 1's
// function to find the index of first '1'
// binary search technique is applied
function indexOfFirstOne(arr, low, high)
{
while (low <= high) {
var mid = parseInt((low + high) / 2);
// if true, then 'mid' is the index of first '1'
if (arr[mid] == 1 && (mid == 0 || arr[mid - 1] == 0))
return mid;
// first '1' lies to the left of 'mid'
else if (arr[mid] == 1)
high = mid - 1;
// first '1' lies to the right of 'mid'
else
low = mid + 1;
}
// 1's are not present in the array
return -1;
}
// Driver program to test above
var arr = [0, 0, 0, 0, 0, 0, 1, 1, 1, 1];
var n = arr.length;
document.write( indexOfFirstOne(arr, 0, n - 1));
// This code is contributed by rrrtnx.
</script>
Producción
6
Complejidad de tiempo: O (Iniciar sesión)
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA