Dado un arreglo y un entero k, recorra el arreglo y si el elemento en el arreglo es k, doble el valor de k y continúe el recorrido. Al final devuelve el valor de k.
Ejemplos:
Input : arr[] = { 2, 3, 4, 10, 8, 1 }, k = 2
Output: 16
Explanation:
First k = 2 is found, then we search for 4
which is also found, then we search for 8
which is also found, then we search for 16.
Input : arr[] = { 2, 4, 5, 6, 7 }, k = 3
Output: 3
Método – 1: (Fuerza bruta)
1) Recorrer cada elemento de una array si arr[i] == k entonces k = 2 * k.
2) Repita el mismo proceso para el valor máximo de k.
3) Por fin Devolver el valor de k.
C++
// C++ program to find value if we double
// the value after every successful search
#include <bits/stdc++.h>
using namespace std;
// Function to Find the value of k
int findValue(int a[], int n, int k)
{
bool exist = true;
// Search for k. After every successful
// search, double k and change exist to true
// and search again for k from the start of array
while(exist){
exist = false;
for (int i = 0; i < n; i++) {
// Check is a[i] is equal to k
if (a[i] == k){
k *= 2;
exist = true;
break;
}
}
}
return k;
}
// Driver's Code
int main()
{
int arr[] = { 2, 3, 4, 10, 8, 1 }, k = 2;
int n = sizeof(arr) / sizeof(arr[0]);
cout << findValue(arr, n, k);
return 0;
}
Java
// Java program to find value
// if we double the value after
// every successful search
class GFG
{
// Function to Find the value of k
static int findValue(int arr[], int n, int k)
{
boolean exist = true;
// Search for k. After every successful
// search, double k and change exist to true
// and search again for k from the start of array
while(exist){
exist = false;
for (int i = 0; i < n; i++) {
// Check is a[i] is equal to k
if (arr[i] == k){
k *= 2;
exist = true;
break;
}
}
}
return k;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 3, 4, 10, 8, 1 }, k = 2;
int n = arr.length;
System.out.print(findValue(arr, n, k));
}
}
// This code is contributed by Aarti_Rathi
C#
using System;
/*
C# program to find value if we double
the value after every successful search
*/
public class GFG {
// Function to Find the value of k
static int findValue(int[] a, int n, int k)
{
bool exist = true;
// Search for k. After every successful
// search, double k and change exist to true
// and search again for k from the start of array
while (exist) {
exist = false;
for (int i = 0; i < n; i++) {
// Check is a[i] is equal to k
if (a[i] == k) {
k *= 2;
exist = true;
break;
}
}
}
return k;
}
// Driver Code
public static void Main()
{
int[] arr = { 2, 3, 4, 10, 8, 1 };
int k = 2;
int n = arr.Length;
Console.WriteLine(findValue(arr, n, k));
}
}
// This code is contributed by Aarti_Rathi
Python3
# Python program to find value if we double # the value after every successful search # Function to Find the value of k def findValue(a, n, k): exist = True while exist: # Search for k. After every successful # search, double k and change exist to true # and search again for k from the start of array exist = False for i in range(n): # Check is a[i] is equal to k if a[i] == k: k *= 2 exist = True break return k # Driver's Code arr = [2, 3, 4, 10, 8, 1] k = 2 n = len(arr) print(findValue(arr, n, k))
Producción
16
Complejidad de tiempo: O (n ^ 2)
Método – 2: (Ordenar y buscar)
1) Ordenar la array
2) Luego puede buscar el elemento en un bucle porque estamos seguros de que k*2 estaría después de k en esta array. Por lo tanto, simplemente multiplique el valor de k allí solo en el ciclo.
C++
// CPP program to find value if we double
// the value after every successful search
#include <bits/stdc++.h>
using namespace std;
// Function to Find the value of k
int findValue(int a[], int n, int k)
{
// Sort the array
sort(a, a + n);
// Search for k. After every successful
// search, double k.
for (int i = 0; i < n; i++) {
// Check is a[i] is equal to k
if (a[i] == k)
k *= 2;
}
return k;
}
// Driver's Code
int main()
{
int arr[] = { 2, 3, 4, 10, 8, 1 }, k = 2;
int n = sizeof(arr) / sizeof(arr[0]);
cout << findValue(arr, n, k);
return 0;
}
Java
// Java program to find value
// if we double the value after
// every successful search
class GFG {
// Function to Find the value of k
static int findValue(int arr[], int n, int k)
{
// Search for k. After every successful
// search, double k.
for (int i = 0; i < n; i++)
if (arr[i] == k)
k *= 2;
return k;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 3, 4, 10, 8, 1 }, k = 2;
int n = arr.length;
System.out.print(findValue(arr, n, k));
}
}
// This code is contributed by
// Smitha Dinesh Semwal
Python3
# Python program to find # value if we double # the value after every # successful search # Function to Find the value of k def findValue(arr, n, k): # Search for k. # After every successful # search, double k. for i in range(n): if (arr[i] == k): k = k * 2 return k # Driver's Code arr = [2, 3, 4, 10, 8, 1] k = 2 n = len(arr) print(findValue(arr, n, k)) # This code is contributed # by Anant Agarwal.
C#
// C# program to find value
// if we double the value after
// every successful search
using System;
class GFG {
// Function to Find the value of k
static int findValue(int[] arr, int n, int k)
{
// Search for k. After every successful
// search, double k.
for (int i = 0; i < n; i++)
if (arr[i] == k)
k *= 2;
return k;
}
// Driver Code
public static void Main()
{
int[] arr = { 2, 3, 4, 10, 8, 1 };
int k = 2;
int n = arr.Length;
Console.WriteLine(findValue(arr, n, k));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find
// value if we double
// the value after every
// successful search
// Function to Find
// the value of k
function findValue($arr, $n, $k)
{
// Search for k. After every
// successful search, double k.
for ($i = 0; $i < $n; $i++)
if ($arr[$i] == $k)
$k *= 2;
return $k;
}
// Driver Code
$arr = array(2, 3, 4, 10, 8, 1);
$k = 2;
$n = count($arr);
echo findValue($arr, $n, $k);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to find value
// if we double the value after
// every successful search
// Function to Find the value of k
function findValue(arr, n, k)
{
// Search for k. After every successful
// search, double k.
for (let i = 0; i < n; i++)
if (arr[i] == k)
k *= 2;
return k;
}
// Driver code
let arr = [ 2, 3, 4, 10, 8, 1 ], k = 2;
let n = arr.length;
document.write(findValue(arr, n, k));
</script>
Producción
16
Complejidad de tiempo: O (nlogn)
Método – 3: (Hashing)
1) Poner todos los elementos en hashmap.
2) Busque si k está en hashmap, si es así, multiplique el valor por k o devuelva el valor de k.
C++
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the value
int findValue(int a[], int n, int k)
{
// Unordered Map
unordered_set<int> m;
// Iterate from 0 to n - 1
for (int i = 0; i < n; i++)
m.insert(a[i]);
while (m.find(k) != m.end())
k = k * 2;
return k;
}
// Driver's Code
int main()
{
int arr[] = { 2, 3, 4, 10, 8, 1 }, k = 2;
int n = sizeof(arr) / sizeof(arr[0]);
cout << findValue(arr, n, k);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
static int findValue(int[] a,int n,int k){
// Unordered set
HashSet<Integer> m = new HashSet<Integer>();
// Iterate from 0 to n - 1
for(int i=0;i<n;i++){
m.add(a[i]);
}
while (m.contains(k)){
k = k * 2;
}
return k;
}
// Drivers code
public static void main(String args[]){
int[] arr = { 2, 3, 4, 10, 8, 1 };
int k = 2;
int n = arr.length;
System.out.println(findValue(arr, n, k));
}
}
// This code is contributed by shinjanpatra.
Python3
# Python program for the above approach # Function to find the value def findValue(a, n, k): # Unordered Map m = set() # Iterate from 0 to n - 1 for i in range(n): m.add(a[i]) while (k in m): k = k * 2 return k # Driver's Code arr, k = [ 2, 3, 4, 10, 8, 1 ], 2 n = len(arr) print(findValue(arr, n, k)) # This code is contributed by shinjanpatra
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
static int findValue(int[] a, int n, int k)
{
// Unordered set
HashSet<int> m = new HashSet<int>();
// Iterate from 0 to n - 1
for (int i = 0; i < n; i++) {
m.Add(a[i]);
}
while (m.Contains(k)) {
k = k * 2;
}
return k;
}
// Drivers code
public static void Main(string[] args)
{
int[] arr = { 2, 3, 4, 10, 8, 1 };
int k = 2;
int n = arr.Length;
Console.WriteLine(findValue(arr, n, k));
}
}
// This code is contributed by Tapesh(tapeshdua420)
Javascript
<script>
// JavaScript program for the above approach
// Function to find the value
function findValue(a, n, k)
{
// Unordered Map
let m = new Set();
// Iterate from 0 to n - 1
for (let i = 0; i < n; i++)
m.add(a[i]);
while (m.has(k))
k = k * 2;
return k;
}
// Driver's Code
let arr = [ 2, 3, 4, 10, 8, 1 ], k = 2;
let n = arr.length;
document.write(findValue(arr, n, k));
// This code is contributed by shinjanpatra<a href="https://www.youtube.com/watch?v=xtfj4-r_Ahs&list=PLqM7alHXFySEQDk2MDfbwEdjd2svVJH9p&ab_channel=GeeksforGeeks">https://www.youtube.com/watch?v=xtfj4-r_Ahs&list=PLqM7alHXFySEQDk2MDfbwEdjd2svVJH9p&ab_channel=GeeksforGeeks</a>
</script>
Producción
16
Complejidad de tiempo: O(n)
Complejidad espacial: O(n)
Referencia: href=”https://www.geeksforgeeks.org/flipkart-interview-experience-set-35-on-campus-for-sde-1/”